Teyberrs

Problem Description

Teyberrs is a paradise for birds to live in. Assume you are a bird in Teyberrs, you are now flying somewhere like the game ''Flappy Bird''. You start flying at $(0,s)$, and every time when you are at $(x-1,y)$ ($1\leq x\leq n$), you must fly to either $(x,y-1)$ with cost $a_x$ or $(x,y+1)$ with cost $b_x$. Like the map in ''Flappy Bird'', you can not hit obstacles at $(x,y)$ where $y < l_x$ or $y > r_x$. You will be given $q$ queries. In each query, you will be given two integers $x$ and $y$. Assume your target is at $(x,y)$, can you find the path with the minimum cost, or determine it is impossible?

Input

The first line contains a single integer $T$ ($1 \leq T \leq 200$), the number of test cases. For each test case: The first line of the input contains three integers $n$, $q$ and $s$ ($1 \leq n,q \leq 200\,000$, $1\leq s\leq n$), denoting the size of the map, the number of queries, and the start point. In the next $n$ lines, the $i$-th line contains four integers $a_i$, $b_i$, $l_i$ and $r_i$ ($1\leq a_i,b_i\leq 10^9$, $1\leq l_i\leq r_i\leq n$). In the next $q$ lines, the $i$-th line contains two integers $x$ and $y$ ($1\leq x,y\leq n$), describing a target point. It is guaranteed that the sum of all $n$ is at most $1\,000\,000$, and the sum of all $q$ is at most $1\,000\,000$.

Output

For each query, print a single line containing an integer, denoting the minimum total cost. When it is impossible to reach the target, please print ''$\texttt{-1}$'' instead.

Sample Input

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

Sample Output

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

Source

2023“钉耙编程”中国大学生算法设计超级联赛（3）