物理学非常有趣！昨天，你的老师解释了干涉是如何工作的：如果你有两列波，它们的波高会在整个波长范围内相加！因此，如果两列波都有波峰，产生的波峰会更高。同样，如果两列波在水面下都有波谷，产生的波谷会更深。从技术上讲，波的高度称为振幅，两个波峰之间的距离称为波长。

今天，你的物理老师描述了她即将进行的实验设置。她将在一个一维水槽中产生驻波。由于她对物理要素的卓越控制，所有波都将具有精确控制的振幅，并且仅在给定长度的区间内产生。每列波的波长始终为 $4$，且第一个正波峰始终位于区间的第一个索引处。我们仅测量整数点处的波振幅。例如，一列振幅为 $2$、长度为 $9$ 的波可以描述为 $2 \ 0 \ -2 \ 0 \ 2 \ 0 \ -2 \ 0 \ 2$。如果某点处没有波，则振幅为 $0$。

你的任务是预测在容器中给定点处，考虑到截至该点产生的所有波，合成波的高度。

图 I.1：样例 2 中三列波的干涉。黑点表示合成波的高度。

输入格式

输入包含： 一行，包含两个整数 $n$ 和 $w$ ($1 \le n \le 4\,000, 1 \le w \le 10^9$)，分别表示操作行数和容器宽度。 $n$ 行，每行包含一个波描述或一个预测任务： “! $p \ \ell \ a$”，一个波描述，起始位置为 $p$，长度为 $\ell$ ($1 \le p, \ell \le w$)，振幅为 $a$ ($1 \le a \le 10^9$)。保证 $p + \ell - 1 \le w$。 “? $p$”，一个预测任务，预测位置 $p$ ($1 \le p \le w$) 处的合成波高度。

参见图 I.1 以获取样例 2 的部分可视化。

输出格式

对于每个预测任务，输出一行，包含一个整数，即在请求位置处由所有先前描述的波产生的合成波高度。

样例

样例输入 1

4 10
! 2 7 1
? 9
? 7
? 6

样例输出 1

0
0
1

样例输入 2

7 10
! 2 6 1
! 3 8 2
! 5 2 3
? 6
! 5 5 4
? 8
? 9

样例输出 2

1
0
2

样例输入 3

6 12
! 1 7 1
! 7 3 2
? 6
? 7
? 8
? 10

样例输出 3

0
1
0
0

样例输入 4

6 11
! 1 6 1
? 6
! 5 7 4
? 6
! 6 3 2
? 6

样例输出 4

0
0
2