В городе, где живет Клеофас, есть известный музей. В этом музее уже давно выставлено n экспонатов (пронумерованных от 1 до n); i-й экспонат имеет ценность vi и массу wi.
Недавно музей купила большая финансовая группа и начала менять набор экспонатов. Примерно в то же время Клеофас... скажем так, заинтересовался этим музеем.
Вам следует обработать q событий трёх типов:
- тип 1 — музей выставляет экспонат ценностью v и массой w; экспонат, появляющийся в i-м событии этого типа, получает номер n + i (смотрите пояснения к примерам);
- тип 2 — музей убирает экспонат номер x и аккуратно относит его в хранилище;
- тип 3 — Клеофас заходит в музей и задаётся вопросом (конечно, без какой-либо конкретной причины): если будет ограбление и украдут экспонаты с общей массой не более m, то какова может быть их максимальная суммарная ценность?
Пусть для каждого события типа 3 s(m) является максимально возможной общей ценностью украденных экспонатов с общей массой ≤ m.
Формально, пусть D — множество номеров всех экспонатов, на данный момент выставленных напоказ (таким образом, изначально D = {1, ..., n}). Пусть P(D) будет множеством всех подмножеств D и пусть
Тогда s(m) определяется как
Вычислите s(m) для каждого 
. Обратите внимание на специальный формат выходных данных.
Выходные данные
Так как количество значений s(m) может оказаться большим, выведите ответы на события типа 3 в особом формате.
Для каждого события типа 3 рассмотрим значения s(m), рассчитанные для вопроса Клеофаса, которым он задался в некоторый момент времени; выведите единственное число
где p = 107 + 19 и q = 109 + 7.
Выводите ответы на события типа 3 в том порядке, в котором они упоминаются во входных данных.
Примечание
В первом примере количество выставленных экспонатов и значения s(1), ..., s(10) для отдельных событий типа 3 таковы, по порядку:
Ценности отдельных экспонатов таковы: v1 = 30, v2 = 60, v3 = 5, v4 = 42, v5 = 20, v6 = 40 и их массы таковы: w1 = 4, w2 = 6, w3 = 1, w4 = 5, w5 = 3, w6 = 6.
Во втором примере единственный вопрос задается после того, как все экспонаты уже убраны, так что s(m) = 0 для любых m.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 10
30 4
60 6
5 1
9
3
1 42 5
1 20 3
3
2 2
2 4
3
1 40 6
3
|
556674384
168191145
947033915
181541912
|
|
2
|
3 1000
100 42
100 47
400 15
4
2 2
2 1
2 3
3
|
0
|