레이팅 미적용Physics can be so much fun! Yesterday, your teacher explained how interference works: If you have two waves, their heights add up over the whole waves' length! So if both waves have a peak, the resulting peak will be even higher. Likewise, if both waves have a wave trough below the water surface, the resulting wave has a trough that will be even further below. Technically, a wave's height is called amplitude and the distance between two wave peaks is called 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. Due to her superior control over physical elements, all waves will have a precisely controlled amplitude and will only be created in an interval of given length. The wavelength of each wave is always \(4\) and the first positive peak will always be at the first index of the interval. We only measure the wave's amplitude 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 is \(0\). Your task is to predict how high the resulting wave will be at given points in the container taking into account all the waves that were created up to that point.
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\).
- A wave is described by "!\(~p~\ell~a\)", (\(1 \le p, \ell \le w\), \(1 \le a \le 10^9\)) the starting position, length, and amplitude of the wave.
- "?\(~p\)", a prediction task for the resulting wave at position \(p\) (\(1 \le p \le w\)).
See Figure for a partial visualization of Sample 2.
For each prediction task, output a line with a single integer, the height of the wave resulting from all former described waves at the requested position.
4 10
! 2 7 1
? 9
? 7
? 6
0
0
1
7 10
! 2 6 1
! 3 8 2
! 5 2 3
? 6
! 5 5 4
? 8
? 9
1
0
2
6 12
! 1 7 1
! 7 3 2
? 6
? 7
? 8
? 10
0
1
0
0
6 11
! 1 6 1
? 6
! 5 7 4
? 6
! 6 3 2
? 6
0
0
2