간섭

물리는 정말 재미있을 수 있다! 어제 선생님이 간섭이 어떻게 일어나는지 설명해 주셨다. 두 파동이 겹치면 파동의 높이는 파동 전체 길이에 걸쳐 더해진다. 두 파동 모두 마루가 있으면 합성파의 마루는 더 높아진다. 같은 방식으로, 두 파동 모두 수면 아래로 내려가 골을 이루면 합성파의 골은 더 깊어진다. 엄밀히 말하면, 파동의 높이를 진폭이라 하고 두 마루 사이의 거리를 파장이라고 한다.

오늘 물리 선생님은 곧 수행할 실험의 설정을 설명한다. 선생님은 1차원 물 수조에 정상파를 만든다. 선생님은 물리 장치를 정밀하게 제어하므로, 모든 파동은 정확히 조절된 진폭을 가지며 주어진 길이의 구간에서만 생성된다. 각 파동의 파장은 항상 $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$은 줄 수이고, $w$는 수조의 너비이다.
• 이후 $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$)에서 합성파의 높이를 묻는 질문이다.

각 예측 질문에 대해, 그 이전에 주어진 모든 파동이 만드는 합성파의 해당 위치 높이를 정수 하나로 한 줄에 출력한다.