提示: 欢迎访问OurACM平台。
Problem 2192 位置信息挖掘

Accept: 133    Submit: 663
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

O2O即Online To Offline,是指将线下的商务机会与互联网结合,让互联网成为线下交易的前台。这些商务机会主要是偏服务类的商品,例如汽车售后服务、摄影服务、餐饮、电影等,其特色是线上购买、线下服务。

因此,对这类垂直行业的商品做移动推荐时,用户和商品的位置信息显得格外重要。但是,可能存在用户、商品的位置信息缺失的情况,例如:用户不共享位置信息、商家未填写位置信息……

现在,Jason给出用户在移动端的购买行为数据,以及商品集合,希望能补全一些缺失的位置信息。为了简化问题,假设:

1、由于是服务类的商品,如果用户位于城市A,那么该用户只会购买位于城市A的商品。

2、数据不存在噪声,即测试数据都是合法的。

Input

包含多组数据

每组输入数据格式如下:

第一行,三个数:N、M、Q,表示N个商品,M条购买行为数据,Q个询问。

接下来N行,每行两个数:itemId、cityId,表示商家填写的服务itemId,位于城市cityId。

接下来M行,每行三个数:userId、itemId、cityId,表示用户userId购买了服务itemId,移动端定位城市cityId。

接下来Q行,每行两个数:0、itemId或者1、userId,表示询问服务itemId所在的城市,或者用户userId所在的城市。

注意:0表示位置信息缺失。

Output

每组输出数据格式如下: Q行,每行一个数:cityId,表示服务itemId位于cityId,或者用户userId位于cityId。

Sample Input

3 2 5 2 0 3 0 1 3 2 2 2 1 1 0 0 1 0 2 0 3 1 1 1 2

Sample Output

3 2 0 3 2

Hint

1<=N<=LIMIT

1<=M<=LIMIT

1<=Q<= N+M

1<=itemId<=N

1<=userId<=M

0<=cityId<=N+M,0表示位置信息缺失

对于60%的数据,LIMIT<=10^2;对于100%的数据,LIMIT<=10^5

Source

福州大学第十二届程序设计竞赛

Submit  Back  Status  Discuss