题目描述

有 $n \times m$ 只白羊排成一个 $n$ 行 $m$ 列的方阵，从上到下分别标号为第 $1, 2, 3, \cdots, n$ 行，从左到右分别标号为第 $1, 2, 3, \cdots, m$ 列。现在，我们要对白羊们染上颜色。

我们共会进行 $p$ 次染色。每次选择五个正整数 $xl$，$yl$，$xr$，$yr$，$c$，然后把从第 $xl$ 到第 $xr$ 行，第 $yl$ 到第 $yr$ 列之间的所有羊都染上一个指定的颜色 $c$。被再次染上的颜色会覆盖掉原来的颜色。

在所有染色结束后，若若子想知道一些指定的羊的颜色。

输入格式

第一行四个正整数 $n$，$m$，$p$，$q$，用一个空格分隔，表示白羊方阵的行数和列数，以及染色和询问的次数。

随后 $p$ 行，每行五个正整数 $xl$，$yl$，$xr$，$yr$，$c$，用空格分隔，表示此次染色的区间范围和颜色。

随后 $q$ 行，每行两个正整数 $x$ 和 $y$，用空格分隔，表示若若子想知道第 $x$ 行第 $y$ 列的羊的颜色。

输出格式

对于每次询问，输出一行一个整数，表示第 $x$ 行第 $y$ 列的羊的颜色。

如果从来没有被染色，则这只羊为白色，以 $0$ 表示。

样例

样例输入

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

样例输出

0
27

数据范围与提示

$1 \leq n, m \leq 10^5$

$1 \leq p \leq 10^5$

$1 \leq q \leq 100$

$1 \leq xl \leq xr \leq n$

$1 \leq yl \leq yr \leq m$

$1 \leq c \leq 10^9$