题目描述

植物的命名分为两部分，为了方便我们将两部分分别视为数字，第一部分的数字为 $1,2,\ldots,n$ 之一，第二部分为 $1,2,\ldots,m$ 之一。

现在给你 $N$ 种植物，第 $i$ 种植物编号为 $i$，每种植物的命名两两互不相同。对于第 $i$ 种植物，你需要找到和他命名第一部分相同的植物中，第二部分第 $k_i$ 小植物的编号，数据保证第 $k_i$ 小的植物存在。

输入格式

第一行输入三个正整数 $N,n,m$。

接下来 $N$ 行，每行两个正整数，表示一种植物的命名。

接下来一行，输入一行 $N$ 个正整数，第 $i$ 个正整数表示 $k_i$。

输出格式

一行 $N$ 个正整数，用空格分开，第 $i$ 个表示你要对第 $i$ 种植物求的答案。

样例 #1

样例输入 #1

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

样例输出 #1

2 3 1 5 5

样例 #2

样例输入 #2

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

样例输出 #2

2 3 1 5 4

样例 #3

样例输入 #3

4 2 2
1 2
2 1
1 1
2 2
1 2 2 1

样例输出 #3

3 4 1 2

提示

对于样例 #1，第一部分为 $1$ 的植物有 $1,2,3$ 三种，对应第二部分分别为 $1,2,3$，第一部分为 $2$ 的植物有 $4,5$ 两种，对应第二部分分别为 $1,2$。故第一部分为 $1$ 的植物中，第二部分第 $2,3,1$ 小的分别是 $2,3,1$ 号植物。第一部分为 $2$ 的植物中第二部分第 $2$ 小的是 $5$ 号植物。

对于样例 #2，第一部分为 $1$ 的植物有 $1,2,3$ 三种，对应第二部分分别为 $1,2,3$，第一部分为 $2$ 的植物有 $4,5$ 两种，对应第二部分分别为 $1,2$。故第一部分为 $1$ 的植物中，第二部分第 $2,3,1$ 小的分别是 $2,3,1$ 号植物。第一部分为 $2$ 的植物中第二部分第 $2,1$ 小的分别是 $5,4$ 号植物。

对于 $30\%$ 的数据，保证 $n=1$。

对于另外 $20\%$ 的数据，保证 $k_i=1$。

对于 $100\%$ 的数据，保证 $1\leq n,m\leq 100$，$1\le N\le 10^4$。