问题 H: Teyberrs

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\le x\le n$), you must fly to either $(x,y-1)$ with cost ax or$(x,y+1)$ with cost bx. Like the map in ''Flappy Bird'', you can not hit obstacles at $(x,y)$ where y<lx or y>rx.

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?

The first line contains a single integer $T$ ($1\le T\le 200$), the number of test cases. For each test case:

The first line of the input contains three integers $n$, $q$ and $s$ ($1\le n,q\le 200,000$, $1\le s\le 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 ai, bi, li and ri (1≤ai,bi≤1e9, 1≤li≤ri≤n).

In the next $q$ lines, the $i$-th line contains two integers $x$ and $y$ ($1\le x,y\le 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

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
2
-1
2
-1
6
-1
-1