Teyberrs 是鸟儿居住的天堂。假设你是一只在 Teyberrs 的鸟，你现在正像玩“Flappy Bird”游戏一样飞行。你从 $(0, s)$ 开始飞行，每当你处于 $(x-1, y)$ ($1 \le x \le n$) 时，你必须飞往 $(x, y-1)$（代价为 $a_x$）或 $(x, y+1)$（代价为 $b_x$）。就像“Flappy Bird”中的地图一样，你不能撞到 $y < l_x$ 或 $y > r_x$ 的障碍物 $(x, y)$。

你将收到 $q$ 次询问。每次询问会给出两个整数 $x$ 和 $y$。假设你的目标点是 $(x, y)$，你能找到代价最小的路径，或者确定其是否无法到达吗？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 200$)，表示测试用例的数量。对于每个测试用例：

第一行包含三个整数 $n, q$ 和 $s$ ($1 \le n, q \le 200\,000, 1 \le s \le n$)，分别表示地图的大小、询问次数和起始点。

接下来的 $n$ 行中，第 $i$ 行包含四个整数 $a_i, b_i, l_i$ 和 $r_i$ ($1 \le a_i, b_i \le 10^9, 1 \le l_i \le r_i \le n$)。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n$)，描述一个目标点。

保证所有 $n$ 的总和不超过 $1\,000\,000$，所有 $q$ 的总和不超过 $1\,000\,000$。

输出格式

对于每次询问，输出一行一个整数，表示最小总代价。如果无法到达目标点，请输出“-1”。

样例

输入 1

1
3 9 2
1 2 1 3
3 1 2 3
4 3 1 2
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

输出 1

1
-1
2
-1
2
-1
6
-1
-1