고전 자료구조 문제

길이가 $2^m$인 정수 배열 $A = [a_0, a_1, \ldots, a_{2^m-1}]$이 있다. 처음에는 모든 원소가 0이다.

정수 변수 $x$도 있으며, 처음에 $x = 0$이다.

각 $i = 1, 2, \ldots, n$에 대해 정수 $p_i$와 $q_i$가 주어지고, 다음 과정을 수행한다.

• $p' = (p_i + x) \bmod 2^m$, $q' = (q_i + x) \bmod 2^m$으로 둔다.
• $l = \min(p', q')$, $r = \max(p', q')$로 둔다.
• $j = l, l+1, \ldots, r$ 각각에 대해 $a_j$에 $i$를 더한 뒤, $x$에 $a_j$를 더한다.

이 과정이 끝났을 때의 $x \bmod 2^{30}$ 값을 구하라.

첫 줄에 두 정수 $n$과 $m$이 주어진다 ($1 \le n \le 500\,000$; $1 \le m \le 30$).

이어지는 $n$개의 줄 중 $i$번째 줄에는 두 정수 $p_i$와 $q_i$가 주어진다 ($0 \le p_i, q_i < 2^m$).

$x \bmod 2^{30}$의 값을 출력한다.

예제 테스트에서 처음에는 $A = [0, 0, 0, 0]$이고 $x = 0$이다. 그다음 과정은 다음과 같다.

• $i = 1$일 때 $l = 1$, $r = 2$이므로 $A = [0, 1, 1, 0]$, $x = 2$가 된다.
• $i = 2$일 때 $l = 1$, $r = 3$이므로 $A = [0, 3, 3, 2]$, $x = 10$이 된다.
• $i = 3$일 때 $l = 0$, $r = 1$이므로 $A = [3, 6, 3, 2]$, $x = 19$가 된다.
• $i = 4$일 때 $l = 0$, $r = 3$이므로 $A = [7, 10, 7, 6]$, $x = 49$가 된다.
• $i = 5$일 때 $l = 1$, $r = 3$이므로 $A = [7, 15, 12, 11]$, $x = 87$이 된다.