치터와 쿼리

$1$번부터 $N$번까지 번호가 붙은 $N$명의 사람이 일렬로 서 있다. 거짓말쟁이들은 정확히 하나의 비어 있지 않은 연속 구간을 이룬다. 즉, 어떤 $1 \leq L \leq R \leq N$이 존재하여 $L,L+1,\cdots,R$번 사람만 거짓말쟁이이다.

$i$번 사람은 $l_i$번부터 $r_i$번까지의 사람 중 적어도 한 명이 거짓말쟁이라고 주장한다.

거짓말쟁이의 주장은 거짓이고, 거짓말쟁이가 아닌 사람의 주장은 참이다.

현재 주장들과 모순되지 않는 거짓말쟁이 구간을 하나 구하여라. 그런 구간이 없다면 그 사실을 판별해야 한다.

사람들의 주장은 여러 번 변경된다. 각 변경 뒤의 주장들에 대해 답을 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

$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$

$j$번 변경에서는 $X_j$번 사람의 주장을 $A_j$번부터 $B_j$번까지의 사람 중 적어도 한 명이 거짓말쟁이라는 주장으로 바꾼다. 즉, $(l_{X_j},r_{X_j})$를 $(A_j,B_j)$로 변경한다.

각 케이스의 각 변경 뒤에 한 줄을 출력한다.

현재 주장들과 모순되지 않는 거짓말쟁이 구간이 없다면 -1을 출력한다.

그런 구간이 있다면 두 정수 $L,R$을 공백으로 구분하여 출력한다. 출력한 $L,R$은 $1 \leq L \leq R \leq N$을 만족해야 하며, 정확히 $L$번부터 $R$번까지의 사람이 거짓말쟁이라고 할 때 모든 사람의 주장이 조건에 맞아야 한다.

가능한 답이 여러 가지라면 아무거나 출력해도 된다.

• $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$).
• 모든 테스트 케이스에 대한 $N+Q$의 합은 $50\,000$ 이하이다.