题目背景

“让我给你最后变一次魔术叭”

“好呀好呀，是什么呢”

“看好喽，3…2…1…”

“我不见啦”

再也见不着啦……

题目描述

食堂是平面上的一个正方形区域，一个点 $(x,y)$ 在食堂内当且仅当 $0\le x,y\le w$。食堂中有 $n$ 面墙，墙没有厚度，可以看成端点为 $(x_1,y_1),(x_2,y_2)$ 的线段。墙要么是水平的，要么是竖直的，即 $x_1=x_2$ 或 $y_1=y_2$。

有 $m$ 个鸽子的朋友正在食堂里吃饭，他们的位置是固定的。而鸽子会找不同的朋友蹭饭，吃饭时可以改变位置。鸽子可以飞过任意多的墙，降落到任意一个朋友所在的位置开始吃饭。一旦开始吃饭，鸽子就不愿意飞，只会去不用飞过墙就能到达的朋友处蹭饭。

鸽子想知道，如果从第 $i$ 个朋友所在的位置开始，不用飞过墙能到达的朋友（包括第 $i$ 个朋友）中编号最小的是多少。

注意：虽然输入的坐标都是整数，但鸽子的蹭饭路线可以经过两维均不为整数的坐标，只要不穿墙。

输入格式

第一行三个正整数 $n,m,w$。

接下来 $n$ 行，每行四个非负整数 $x_1,y_1,x_2,y_2$，表示一面墙的两个端点。

接下来 $m$ 行，每行两个正整数 $u,v$，表示鸽子朋友的坐标为 $(u,v)$。

输出格式

$m$ 行，第 $i$ 行一个正整数，表示如果从第 $i$ 个朋友所在的位置开始，不用飞过墙能到达的朋友的最小编号。这个编号应当在 $1\sim i$ 之间。

样例一

input

10 7 9
3 0 3 8
9 0 9 9
6 3 6 6
3 6 6 6
6 6 7 6
0 0 0 9
3 3 8 3
4 3 9 3
0 9 9 9
0 0 9 0
1 2
4 2
8 4
8 2
4 2
5 5
4 5

output

1
2
1
2
2
6
6

下发文件

限制与约定

保证 $4\le n\le 2\times 10^5$，$1\le m\le 2\times 10^5$，$2\le w\le 10^9$。

保证 $0\le x_1\le x_2\le w$，$0\le y_1\le y_2\le w$，$x_1=x_2$ 或 $y_1=y_2$，但 $(x_1,y_1)\neq (x_2,y_2)$。在输入的 $n$ 条线段中，一定会出现食堂的边界，即 $0,0,0,w$，$0,0,w,0$，$w,0,w,w$，$0,w,w,w$。线段可能相交、包含甚至完全相同。

保证 $1\le u,v\le w-1$。可能有不同朋友在相同位置吃饭，但不可能有朋友卡在墙里吃饭，即输入的点不和任何输入的线段相交。

特殊性质 A：保证输入的水平线段和竖直线段只有不超过 $5\times 10^5$ 个交点（相同坐标只算一个）。