Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Добро пожаловать домой, Ктолли
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

— Я... Я выжила.

— С возвращением домой, Ктолли.

— Я сдержал своё обещание.

— Я сделала это... Я сделала это!

После нескольких дней битвы Ктолли Нота Сениориус чудом вернулась с поля боя живой.

Уильям, как и обещал, готовит торт для неё.

Хоть Уильям и отлично готовит десерты, он плохо умеет готовить торты.

На этот рад Уильям допустил серьёзную ошибку: он сломал духовой шкаф!

К счастью, Ктолли решила помочь ему.

Уильям выложил в ряд n тортов на стол, торты пронумерованы от 1 до n, торт с номером i должен выпекаться ai секунд.

Уильяму нужна помощь Ктолли, чтобы выполнить m операций для выпекания тортов. Каждая операция бывает одного из двух типов.

Тип 1: 1 l r x

Уильям просит Ктолли проверить все торты на отрезке [l, r]. Если некоторый торт должен готовиться дольше чем x секунд, он поместит его на x секунд в духовой шкаф, а затем вернёт на прежнее место.

Более формально, для каждого i на отрезке [l, r] если ai строго больше x, ai становится равным ai - x.

Тип 2: 2 l r x

Уильям спрашивает Ктолли количество тортов на отрезке [l, r] таких, что они должны выпекаться ещё ровно x секунд. Более формально, вы должны найти количество таких i на отрезке [l, r], что ai = x.

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

В первой строке содержатся два целых числа n и m (1 ≤ n, m ≤ 105).

Во второй строке содержатся n целых чисел, i-е из которых обозначает ai (1 ≤ ai ≤ 105).

В следующих m строках даны описания m операций, формат которых описан выше. Гарантируется, что 1 ≤ l ≤ r ≤ n, а также 1 ≤ x ≤ 105.

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

Для каждой операции второго типа выведите ответ.

Примеры
Входные данные
5 6
1 5 5 5 8
2 2 5 5
1 2 4 3
2 2 5 2
2 2 5 5
1 3 5 1
2 1 5 1
Выходные данные
3
3
0
3
Входные данные
7 7
1 9 2 6 8 1 7
2 1 7 1
2 2 5 2
1 4 7 7
2 2 4 2
1 3 4 5
2 3 3 3
2 3 7 2
Выходные данные
2
1
1
0
1
Входные данные
8 13
75 85 88 100 105 120 122 128
1 1 8 70
2 3 8 30
1 3 8 3
2 2 5 15
1 2 4 10
2 1 5 5
1 2 7 27
2 1 5 5
1 3 7 12
1 1 7 4
2 1 8 1
1 4 8 5
2 1 8 1
Выходные данные
1
2
3
4
5
6