B. Ремонт фабрики
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Фабрика производит однодневные дырявые кастрюли. Обычно за один день производится a кастрюль, но сейчас часть оборудования, делающего дырки, сломалась, поэтому производство упало до b кастрюль в день. Руководство фабрики собирается выбрать k последовательных дней и произвести ремонт оборудования. Во время ремонта фабрика не будет ничего производить, зато после его окончания вернётся к производству a кастрюль в день.

Изначально у фабрики нет никаких заказов. Запросы di, ai означают, что ai новых заказов поступило на день di. Для каждого заказа требуется ровно одна однодневная дырявая кастрюля, и, разумеется, она должна быть произведена ровно в этот день (на следующий день кастрюля уже выходит из строя). Фабрика может каждый день удовлетворить любое количество заказов, не превосходящее её производственные мощности для этого дня.

Также в некоторые моменты времени владелец фабрики хочет для некоторого pi знать максимальное количество заказов, которое может быть удовлетворено, если ремонт фабрики будет произведён в дни pi, pi + 1, ..., pi + k - 1.

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

В первой строке входных данных записаны пять целых чисел n, k, a, b и q (1 ≤ k ≤ n ≤ 200 000, 1 ≤ b < a ≤ 10 000, 1 ≤ q ≤ 200 000) — количество дней, продолжительность ремонта, полная и текущая мощности фабрики и количество запросов соответственно.

В следующих q строках идут запросы двух видов:

  • 1 di ai (1 ≤ di ≤ n, 1 ≤ ai ≤ 10 000), означает, что ai заказов поступило на день di.
  • 2 pi (1 ≤ pi ≤ n - k + 1), означает, что владелец хочет знать, сколько заказов может быть выполнено, если первым днём ремонта фабрики будет pi.

Гарантируется, что во входных данных содержится хотя бы один запрос второго типа.

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

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

Примеры
Входные данные
5 2 2 1 8
1 1 2
1 5 3
1 2 1
2 2
1 4 2
1 3 2
2 1
2 3
Выходные данные
3
6
4
Входные данные
5 4 10 1 6
1 1 5
1 5 5
1 3 2
1 5 2
2 1
2 2
Выходные данные
7
1
Примечание

Рассмотрим первый пример.

Фабрика производит не больше 1 однодневной дырявой кастрюли в день и будет производить 2 после ремонта. Ремонт занимает 2 дня.

Для первого запроса мы можем выполнить 1 заказ в день 1, 0 заказов в дни 2 и 3, поскольку будет производиться ремонт, 0 заказов в день 4, поскольку ни одна кастрюля не была заказана на этот день, и 2 заказа в день 5, поскольку больше чем 2 кастрюли в день фабрика произвести не может. Таким образом, будут выполнены 3 заказа.

В третьем запросе мы можем выполнить 1 заказ в день 1, 1 заказ в день 2 и 2 заказа в день 5. В итоге будут выполнены 4 заказа.