题目描述

有一个长度无限长的自然数序列$A$，下标从$0$开始。

初始时所有数均为$0$。先进行$n$次修改，然后进行$m$次查询。

每次修改给出三个数$l,r,x$，将 $A_l,A_{1+1},...,A_r$中的每一个数变成它与$x$的异或值.

每次查询给出一个数字$p$表示查询$A_p$的值。

输入描述

第一行输入两个整数$n,m(1\le n,m\le 10^4)$，意义如上文所述。

接下来$n$行输入$3$个整数$l,r,x(1\le r,0\le l\le r\le 10^{18},0\le x\le 10^9)$，意义如上文所述。

接下来$m$行输入$1$个整数$p(0\le p\le 10^{18})$，意义如上文所述。

输出描述

输出$m$行每行一个整数，表示答案。

样例

输入

2 2
1 5 1
3 7 2
4
6

输出

3
2

样例解释

初始时所有数均为$0$第$1$次修改$A_1\sim A_5，x$为$1$，则将$A_1\sim A_5$的值修改为和$1$的异或值，

当前序列的为$0,1,1,1,1,1,0.......$第$2$次修改$A_3\sim A_7,x$为$2$，

则将$A_3\sim A_7$的值修改为和$2$的异或值，当前序列的为$0,1,1,3,3,3,2$.查询$A_4$和$A_6$的值为$3$和$2$。