eolymp
bolt
Try our new interface for solving problems
Problems

Fabrozavrs-designers

Fabrozavrs-designers

Time limit 3 seconds
Memory limit 122 MiB

Fabrozavrs are known for their fine artistic taste and landscaping hobby. They live near the very picturesque river and now and then reconstruct the path that runs along the river, either pour more land, or tear it, that is. To facilitate this work, they have divided the entire path into the horizontal sections numbered from 1 to n, and their rework is always arranged in the same way: they choose the part of the road from L-th to R-th section (inclusively) and change (reduce or increase) the height in all these areas at the same quantity (if before the rework the heights were different, then the heights will remain different after the rework).

Since, as stated, fabrozavrs have fine artistic taste, each of them thinks that their river is best looking from a certain height. Therefore, they want to know whether there exist in the vicinity of their home the location on the path, where the height is optimal. Help them to figure it out.

Input data

First line contains two numbers n and m (1n, m10^5) - the length of the road and the number of queries. Second line contains n integers - the initial heights of the road's sections; the heights do not exceed 10^4 by absolute value. Each of the next m lines contains one query.

Query + L R X means that the height of road's sections from L-th to R-th (inclusively) should be changed by X. Herewith 1LRn, а |X| ≤ 10^4.

Query ? L R X means that you need to check whether there exist between L-th and R-th sections (inclusively) the road on height exactly X. It is guaranteed that 1LRn and |X| ≤ 10^9.

Output data

For each question of the second type print in the separate line "YES" (without quotes) if the area with desired height exist and "NO" otherwise.

Examples

Input example #1
10 5
0 1 1 3 3 3 2 0 0 1
? 3 5 2
+ 1 4 1
? 3 5 2
+ 7 10 2
? 9 10 3
Output example #1
NO
YES
YES