Given an array a of length n (\(1 <= n <= 10^ 6\), \(1 <= a_i <= 10^9\)). Also given m (\(1 <= m <= 500\)) queries like +, l, r, k (\(1 < ;= l <= r <= n\), \(-10^9 <= k <= 10^9\) ) and queries like ?, l, r, k ( \(1 <= l <= r <= n\), \(-10^9 <= k <= 10^9\) ).
In the first case, you need to add to the numbers in the segment from l to r inclusive, the number k.
In the second case, you need to print 1 if there is a number k on the segment from l to r inclusive, otherwise print 0.
Elements are numbered from 1 to n.
It is guaranteed that after any request, any element of the a array lies within the range of \(-10^9\) up to \(10^9\) inclusive.
Examples
| # |
Input |
Output |
| 1 |
5
1 2 1 1 3
3
|
0
1 |