Interference

Physics can be so much fun! Yesterday, your teacher explained how interference works. When two waves overlap, their heights add up over the whole length of the waves. If both waves have a peak, the resulting peak is even higher. Likewise, if both waves dip below the water surface, the resulting wave dips even further. Technically, a wave's height is called its amplitude, and the distance between two wave peaks is called its wavelength.

Today, your physics teacher describes the setup of an experiment she is about to perform. She will create stationary waves in a one-dimensional container of water. Because she controls the physical setup precisely, every wave has a precisely controlled amplitude and is created only in an interval of a given length. The wavelength of each wave is always $4$, and the first positive peak is always at the first index of the interval. The amplitude is measured only at integer points. For example, a wave with amplitude $2$ and length $9$ can be described as 2 0 -2 0 2 0 -2 0 2. If there is no wave at a point, the amplitude there is $0$. Your task is to predict how high the resulting wave is at given points in the container, taking into account all waves created up to that point.

Figure I.1: Interference of three waves in Sample Input 2. The black dots represent the resulting wave's height.

The input consists of:

• One line with two integers $n$ and $w$ ($1 \le n \le 4\,000$, $1 \le w \le 10^{9}$), the number of lines and the width of the container.
• $n$ lines, each containing either a wave description or a prediction task:
  • ! $p$ $\ell$ $a$: a wave description with starting position $p$, length $\ell$ ($1 \le p, \ell \le w$), and amplitude $a$ ($1 \le a \le 10^9$). It is guaranteed that $p+\ell - 1 \le w$.
  • ? $p$: a prediction task for the resulting wave at position $p$ ($1 \le p \le w$).

For each prediction task, output one line containing a single integer: the height of the resulting wave at the requested position, produced by all waves described before it.