你有一个长度为 $2^m$ 的整数数组 $A = [a_0, a_1, \dots, a_{2^m-1}]$。初始时，数组中的所有元素均为零。 你还有一个整数变量 $x$。初始时，$x = 0$。

对于每个 $i = 1, 2, \dots, n$，给定两个整数 $p_i$ 和 $q_i$，你需要执行以下步骤：

• 令 $p' = (p_i + x) \pmod{2^m}$ 且 $q' = (q_i + x) \pmod{2^m}$。
• 令 $l = \min(p', q')$ 且 $r = \max(p', q')$。
• 对于每个 $j = l, l + 1, \dots, r$，将 $a_j$ 增加 $i$，然后将 $x$ 增加 $a_j$。

求此过程结束时 $x \pmod{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 \pmod{2^{30}}$ 的值。

样例

样例输入 1

5 2
2 1
1 3
3 2
1 0
0 2

样例输出 1

87

说明

在样例测试中，初始时 $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$。