D. Заползание на дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Улитки взбираются на дерево. Высота дерева $$$h$$$ метров, а улитки начинают с позиции $$$0$$$.

Каждая улитка задается парой целых чисел $$$a$$$ и $$$b$$$ ($$$a > b$$$). Начиная с $$$1$$$-го дня, одна улитка взбирается на дерево так: в светлое время суток она поднимается вверх на $$$a$$$ метров; ночью улитка отдыхает и сползает на $$$b$$$ метров. Если в $$$n$$$-й день улитка впервые достигает позиции $$$h$$$ (то есть вершины дерева), то она заканчивает взбираться, и мы говорим, что улитка залезает на дерево за $$$n$$$ дней. Обратите внимание, что в последний день улитка не обязательно поднимается вверх на $$$a$$$ метров, если ее расстояние до вершины меньше $$$a$$$.

К сожалению, изначально вы не знаете точную высоту дерева $$$h$$$, но знаете, что $$$h$$$ — положительное целое число. Вам нужно обработать следующие $$$q$$$ событий по порядку.

  • Событие типа $$$1$$$: приходит улитка с параметрами $$$a$$$ и $$$b$$$ и утверждает, что залезла на дерево за $$$n$$$ дней. Если это утверждение противоречит ранее принятой информации (то есть не существует дерева, для которого все ранее принятые утверждения, а также данное, верны), игнорируйте его. В противном случае примите данное утверждение.
  • Событие типа $$$2$$$: приходит улитка с параметрами $$$a$$$ и $$$b$$$ и спрашивает, сколько дней она будет залезать на дерево. Вы можете дать ответ только на основе принятый вами на текущий момент информации. Если вы не можете точно определить ответ, сообщите об этом.

Вам нужно обработать все события по порядку.

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Затем следует их описание.

Первая строка каждого набора входных данных содержит одно целое число $$$q$$$ ($$$1\le q \le 2\cdot 10^5$$$) — количество событий.

Для следующих $$$q$$$ строк первое целое число в каждой строке равно $$$1$$$ или $$$2$$$ — типу события.

Если тип события равен $$$1$$$, то далее следуют три целых числа $$$a$$$, $$$b$$$ и $$$n$$$ ($$$1\le a,b,n \le 10^9$$$, $$$a>b$$$).

Если тип события равен $$$2$$$, то далее следуют два целых числа $$$a$$$ и $$$b$$$ ($$$1\le a,b \le 10^9$$$, $$$a>b$$$).

Гарантируется, что сумма $$$q$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$q$$$ целых чисел — по одному на каждое событие по порядку.

  • Для каждого события $$$1$$$, если вы принимаете утверждение, выведите $$$1$$$; если вы игнорируете его, выведите $$$0$$$.
  • Для каждого события $$$2$$$ выведите целое число, обозначающее количество дней, которое улитка будет забираться на дерева. Если нельзя определить ответ, выведите $$$-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
Примечание

В первом наборе входных данных мы можем определить $$$h=7$$$ по первому событию, поэтому мы знаем, что второй и третьей улиткам нужно потратить $$$2$$$ и $$$5$$$ дней соответственно, чтобы достичь вершины.

Покажем, как забирается вторая улитка:

  • В светлое время суток $$$1$$$-го дня: поднимается на $$$4$$$ метра, теперь на позиции $$$4$$$.
  • Ночью $$$1$$$-го дня: сползает вниз на $$$1$$$ метр, теперь в позиции $$$3$$$.
  • В светлое время суток $$$2$$$-го дня: поднимается на $$$4$$$ метра, теперь на позиции $$$7$$$ (достигает вершину).

В третьем наборе входных данных сообщение второй улитки противоречит сообщению первой улитки, потому что вторая улитка говорит, что потратила $$$3$$$ дня, а за первые $$$3$$$ дня она может подняться не более чем на $$$1+1+2=4$$$ метра. Однако первой улитке требуется всего $$$1$$$ день, чтобы подняться на $$$4$$$ метра.