#453 Cheaters and Queries

Statement

Statement language

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.

Input

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

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

Output

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 to are liars.

Constraints

$1 \leq T \leq 20$ .
$1 \leq N \leq 50\,000$ .
$1 \leq Q \leq 50\,000$ .

Subtasks

#	Score	Constraints
1	18	$N \leq 40$ . $Q \leq 40$ . The sum of $N+Q$ over all test cases does not exceed .

Samples

Input

Output

After the first change, no liar segment satisfies all conditions.

After the second change, person $1$ alone can be the liar. The same segment remains valid after each of the next two changes.