Улитки взбираются на дерево. Высота дерева \(h\) метров, а улитки начинают с позиции \(0\).
Каждая улитка задается парой целых чисел \(a\) и \(b\) (\(a > b\)). Начиная с \(1\)-го дня, одна улитка взбирается на дерево так: в светлое время суток она поднимается вверх на \(a\) метров; ночью улитка отдыхает и сползает на \(b\) метров. Если в \(n\)-й день улитка впервые достигает позиции \(h\) (то есть вершины дерева), то она заканчивает взбираться, и мы говорим, что улитка залезает на дерево за \(n\) дней. Обратите внимание, что в последний день улитка не обязательно поднимается вверх на \(a\) метров, если ее расстояние до вершины меньше \(a\).
К сожалению, изначально вы не знаете точную высоту дерева \(h\), но знаете, что \(h\) — положительное целое число. Вам нужно обработать следующие \(q\) событий по порядку.
- Событие типа \(1\): приходит улитка с параметрами \(a\) и \(b\) и утверждает, что залезла на дерево за \(n\) дней. Если это утверждение противоречит ранее принятой информации (то есть не существует дерева, для которого все ранее принятые утверждения, а также данное, верны), игнорируйте его. В противном случае примите данное утверждение.
- Событие типа \(2\): приходит улитка с параметрами \(a\) и \(b\) и спрашивает, сколько дней она будет залезать на дерево. Вы можете дать ответ только на основе принятый вами на текущий момент информации. Если вы не можете точно определить ответ, сообщите об этом.
Вам нужно обработать все события по порядку.
Выходные данные
Для каждого набора входных данных выведите \(q\) целых чисел — по одному на каждое событие по порядку.
- Для каждого события \(1\), если вы принимаете утверждение, выведите \(1\); если вы игнорируете его, выведите \(0\).
- Для каждого события \(2\) выведите целое число, обозначающее количество дней, которое улитка будет забираться на дерева. Если нельзя определить ответ, выведите \(-1\).
Примечание
В первом наборе входных данных мы можем определить \(h=7\) по первому событию, поэтому мы знаем, что второй и третьей улиткам нужно потратить \(2\) и \(5\) дней соответственно, чтобы достичь вершины.
Покажем, как забирается вторая улитка:
- В светлое время суток \(1\)-го дня: поднимается на \(4\) метра, теперь на позиции \(4\).
- Ночью \(1\)-го дня: сползает вниз на \(1\) метр, теперь в позиции \(3\).
- В светлое время суток \(2\)-го дня: поднимается на \(4\) метра, теперь на позиции \(7\) (достигает вершину).
В третьем наборе входных данных сообщение второй улитки противоречит сообщению первой улитки, потому что вторая улитка говорит, что потратила \(3\) дня, а за первые \(3\) дня она может подняться не более чем на \(1+1+2=4\) метра. Однако первой улитке требуется всего \(1\) день, чтобы подняться на \(4\) метра.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
1 3 2 5
2 4 1
2 3 2
3
1 6 5 1
2 3 1
2 6 2
3
1 4 2 2
1 2 1 3
2 10 2
9
1 7 3 6
1 2 1 8
2 5 1
1 10 9 7
1 8 1 2
1 10 5 8
1 10 7 7
2 7 4
1 9 4 2
9
1 2 1 6
1 8 5 6
1 4 2 7
2 9 1
1 5 1 4
1 5 2 7
1 7 1 9
1 9 1 4
2 10 8
|
1 2 5
1 -1 1
1 0 1
1 0 -1 0 0 0 1 8 0
1 0 0 1 0 0 0 0 1
|