You are trapped on the top of a 2D grid! The grid consists of $N$ rows and $M$ columns. Each cell either contains an obstacle or is empty. Initially all cells are empty.

Given $K$ triples ${X_i,L_i,R_i}$, meaning you will add obstacles to cells $(L_i, L_i+1, ... ,R_i)$ in row $X_i$. Note that the obstacles may overlap.

The rescue team planned to set up portals to help you escape. However, as the rescue team did not know the structure inside the grid, they are not sure if the location of the portal is suitable. They have $Q$ plans of locations of the portal. the $j$-th plan is to set up the portal in cell $B_j$ of row $A_j$. A location is suitable only if there is no obstacles in that cell and you can fall from the top of the grid to the portal vertically without hitting any obstacles.

You are so scared and want to get out of this place as soon as possible. Please answer the rescue team whether each location of the portal is suitable.

Notice the unsual time limit!!!

Input Specification

The first line consists of three integers $N$, $M$ and $K$, where $N$ and $M$ are the dimensions of the grid and $K$ is the number of triples indicating the position of obstacles.
The next $K$ lines consists of three integers $X_i$, $L_i$ and $R_i$, the triples indication positions of obstacles.
The next line consists of a integer $Q$, the number plans of location of the portal.
The next $Q$ lines consists of two integers $A_j$ and $B_j$, the planned locations of the portal.

Output Specification

Output $Q$ lines. If the $j$-th plan is suitable, output 1, or else output 0.

Subtasks

For all cases,
$1\le N,M,K,Q \le 10^5$
$1\le X_i, A_j \le N$
$1\le B_j \le M$
$1\le L_i \le R_i \le M$

Subtask 1: $K=1$ ($10$ pts)
Subtask 2: $N,M,K\le 1000$, $Q\le 5$ ($20$ pts)
Subtask 3: $N,M,K\le 1000$ ($20$ pts)
Subtask 4: $Q\le 5$ ($20$ pts)
Subtask 5: No additional constraints ($30$ pts)