던전 공략

레몬 왕국의 용사 비타로는 던전을 공략해 레벨을 올리려고 한다.

던전은 $N$개가 있다. $i$번 던전의 난이도는 두 정수 $A_i,B_i$로 표현된다. 현재 레벨이 $X$일 때 $i$번 던전을 공략하면 다음과 같은 결과를 얻는다.

• $X \le A_i$라면 공략에 실패하며, 레벨은 변하지 않는다.
• $B_i \le X$라면 공략에 성공하며, 레벨이 $$만큼 증가한다.

한 번 시도한 던전은 다시 시도할 수 없다. 던전을 시도하는 순서와 시도할 던전의 수는 자유롭게 정할 수 있다.

비타로의 초기 레벨은 $L$이다. 처음 주어진 던전 상태와 각 수정 질의가 적용된 뒤의 던전 상태에 대해, 레벨 $L$에서 시작하여 도달할 수 있는 레벨의 최댓값을 각각 구하여라.

각 답을 구할 때 비타로는 항상 레벨 $L$에서 시작하며, 모든 던전은 아직 시도하지 않은 상태이다. 한 답을 구하는 과정에서 시도한 던전은 다른 답을 구하는 과정에 영향을 주지 않는다.

각 수정 질의는 세 정수 $i,a,b$로 주어진다. 이 질의가 적용되면 $i$번 던전의 난이도가 $A_i=a$, $B_i=b$로 변경된다. 변경된 값은 이후의 질의에도 유지된다.

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

$N\ Q\ L$ $A_1\ B_1$ $$

$Q+1$개의 줄을 출력한다.

첫째 줄에는 수정 질의를 하나도 적용하지 않았을 때 도달할 수 있는 레벨의 최댓값을 출력한다.

그 다음 $Q$개의 줄 중 $q$번째 줄에는 $q$번 질의까지 적용한 뒤 도달할 수 있는 레벨의 최댓값을 출력한다.

• $1 \le N \le 500\,000$.
• $0 \le Q \le 200\,000$.
• $1\le L\le {}^{}$.