Cheaters and Queries

There are $N$ people standing in a line, numbered from $1$ to $N$. The liars form exactly one nonempty contiguous segment. In other words, there exist integers $1 \leq L \leq R \leq N$ such that exactly the people numbered $L,L+1,\cdots,R$ are liars.

Person $i$ claims that at least one person numbered from $l_i$ to $r_i$ is a liar.

Every liar makes a false claim, and every person who is not a liar makes a true claim.

Find one liar segment consistent with all current claims. If no such segment exists, determine that it is impossible.

The claims are changed several times. After every change, print an answer for the current claims.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N\ Q$ $l_1\ r_1$ $l_2\ r_2$ $\vdots$ $l_N\ r_N$ $X_1\ A_1\ B_1$ $X_2\ A_2\ B_2$ $\vdots$ $X_Q\ A_Q\ B_Q$

In the $j$-th change, person $X_j$ changes their claim to say that at least one person numbered from $A_j$ to $B_j$ is a liar. That is, $(l_{X_j},r_{X_j})$ is replaced by $(A_j,B_j)$.

After every change in every test case, print one line.

If no liar segment is consistent with the current claims, print -1.

Otherwise, print two integers $L$ and $R$ separated by a space. They must satisfy $1 \leq L \leq R \leq N$, and every claim must have the required truth value when exactly the people numbered from $L$ to $R$ are liars.

If there are multiple solutions, print any of them.

• $1 \leq T \leq 20$.
• $1 \leq N \leq 50\,000$.
• $1 \leq Q \leq 50\,000$.
• $1 \leq l_i \leq r_i \leq N$ ($1 \leq i \leq N$).
• $1 \leq X_j \leq N$ ($1 \leq j \leq Q$).
• $1 \leq A_j \leq B_j \leq N$ ($1 \leq j \leq Q$).
• The sum of $N+Q$ over all test cases does not exceed $50\,000$.