There are $n$ intervals $[L_i, R_i]$, and there are $m$ cutting operations. Each operation is described by a triple $(x, l, r)$, which performs the following on each $i \in [l, r]$:

• If $x \not\in [L_i, R_i]$, do nothing.
• Otherwise, interval $i$ is cut into two segments $[L_i, x]$ and $[x, R_i]$. The longer segment is chosen as the new interval $i$. If the lengths are equal, $[L_i, x]$ is chosen.

Find the left and right endpoints of each interval after all operations. To simplify the problem, it is guaranteed that all $x$ form a permutation of $1 \sim m$.

The first line contains three integers $n, m, id$ ($1 \le n \le 10^5, 1 \le m \le 10^6, 0 \le id \le 7$), where $id$ is the subtask number (in the sample, $id=0$).

The next $n$ lines each contain two integers $L_i, R_i$ ($1 \le L_i < R_i \le m$), representing the left and right endpoints of interval $i$.

The next $m$ lines each contain three integers $x, l, r$ ($1 \le x \le m, 1 \le l \le r \le n$), representing a cutting operation. It is guaranteed that all $x$ form a permutation of $1 \sim m$.

Output $n$ lines, where the $i$-th line contains two integers representing the final left and right endpoints of interval $i$.

Examples

Input 1

1 4 0
1 4
1 1 1
4 1 1
3 1 1
2 1 1

Output 1

1 2

Input 2

5 5 0
2 3
4 5
1 4
2 5
2 4
1 5 5
2 5 5
3 1 1
5 4 5
4 2 2

Output 2

2 3
4 5
1 4
2 5
2 4

Input 3

ex_cut3.in

Output 3

ex_cut3.out

Note

Satisfies the constraints of subtask 2.

Input 4

ex_cut4.in

Output 4

ex_cut4.out

Note

Satisfies the constraints of subtask 3.

For all data:

$1 \le n \le 10^5, 1 \le m \le 10^6$

$1 \le L_i < R_i \le m, 1 \le x \le m, 1 \le l \le r \le n$, and all $x$ form a permutation of $1 \sim m$.

Special Property A: All $x$ form a random permutation of $1 \sim m$.

Special Property B: For every operation, $l=1$ and $r=n$.