Задача D. Фаброзавры-дизайнеры ≡

Условие

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

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

Формат входного файла

Первая строка входного файла содержит два числа N и M — длину дороги и количество запросов соответственно (1 ≤ N, M ≤ 10⁵). На второй строке содержатся N чисел, разделенных пробелами  — начальные высоты соответствующих частей дороги; высоты не превосходят 10⁴ по модулю. В следующих M строках содержатся запросы по одному на строке. Запрос + L~R~X означает, что высоту частей дороги от L-ой до R-ой (включительно) нужно изменить на X. При этом 1 ≤ L ≤ R ≤ N, а |X| ≤ 10⁴. Запрос ? L~R~X означает, что нужно проверить, есть ли между L-ым и R-ым участками (включая эти участки) участок, где дорога проходит точно на высоте X. Гарантируется, что 1 ≤ L ≤ R ≤ N, а |X| ≤ 10⁹.

Формат выходного файла

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

Примеры тестов

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

NO
YES
YES