eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Фаброзавры-дизайнеры

Фаброзавры-дизайнеры

Лимит времени 3 секунды
Лимит использования памяти 122 MiB

Фаброзавры известны своим тонким художественным вкусом и увлечением ландшафтным дизайном. Они живут около очень живописной реки и то и дело перестраивают тропинку, идущую вдоль реки: либо насыпают дополнительной земли, либо срывают то, что есть. Для того, чтобы упростить эти работы, они поделили всю тропинку на горизонтальные участки пронумерованные от 1 до n, и их переделки устроены всегда одинаково: они выбирают часть дороги от L-го до R-го участка (включительно) и изменяют (уменьшают или увеличивают) высоту на всех этих участках на одну и ту же величину (если до начала переделки высоты были разными, то и после переделки они останутся разными).

Поскольку, как говорилось, у фаброзавров тонкий художественный вкус, каждый из них считает, что их река лучше всего выглядит с определённой высоты. Поэтому им хочется знать, есть ли поблизости от их дома место на тропинке, где высота на их взгляд оптимальна. Помогите им в этом разобраться.

Входные данные

Первая строка содержит два числа n и m (1n, m10^5) - длину дороги и количество запросов соответственно. Во второй строке содержится n чисел - начальные высоты соответствующих частей дороги; высоты не превосходят 10^4 по модулю. В следующих m строках содержатся запросы по одному в строке.

Запрос + L R X означает, что высоту частей дороги от L-ой до R-ой (включительно) нужно изменить на X. При этом 1LRn, а |X| ≤ 10^4.

Запрос ? L R X означает, что нужно проверить, есть ли между L-ым и R-ым участками (включая эти участки) участок, где дорога проходит точно на высоте X. Гарантируется, что 1LRn, а |X| ≤ 10^9.

Выходные данные

На каждый запрос второго типа нужно вывести в отдельной строке слово "YES" (без кавычек), если нужный участок существует, и "NO" в противном случае.

Пример

Входные данные #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
Выходные данные #1
NO
YES
YES