说明

在一个 n*m 的矩阵（矩阵中左上角为第 0 行第 0 列）中，有 k 个格子被涂黑，其他均为白色。现在有 q 次询问，且询问有两种：

• 第一种：输出第 x 行的所有被涂黑的格子的列号。
  
• 第二种：输出第 x 列的所有被涂黑的格子的行号。
  
  

输入格式

第一行为 4 个数 n,m,k,q，含义如前所示。
接下来 k 行每行两个整数 x,y，表示矩阵中第 x 行第 y 列的格子被涂黑。保证任意两个格子不重复。
接下来 q 行每行两个整数 p,x，若 p 为 1 表示第一种询问，p 为 2 表示第二种询问。

输出格式

按照询问的要求输出。若有多个满足条件的格子，按照这些格子被涂黑的先后顺序输出。

样例

5 5 10 4
3 1
5 4
5 1
3 2
1 2
4 3
5 5
2 4
5 2
4 5
1 3
2 2
1 5
2 3

1 2 
3 1 5 
4 1 5 2 
4 

提示

数据范围

• 1<= n,m,q <= 10^5, 1<=k<=min(510^5, nm)。
  
• 数据保证所有询问中输出的格子总个数不超过 5*10^6。