CF1810D.Climbing the Tree

The snails are climbing a tree. The tree height is $h$ meters, and snails start at position $0$.

Each snail has two attributes $a$ and $b$ ($a \gt b$). Starting from the $1$-st day, one snail climbs the tree like this: during the daylight hours of the day, he climbs up $a$ meters; during the night, the snail rests, and he slides down $b$ meters. If on the $n$-th day, the snail reaches position $h$ for the first time (that is, the top of the tree), he will finish climbing, and we say that the snail spends $n$ days climbing the tree. Note that on the last day of climbing, the snail doesn't necessarily climb up $a$ meters, in case his distance to the top is smaller than $a$.

Unfortunately, you don't know the exact tree height $h$ at first, but you know that $h$ is a positive integer. There are $q$ events of two kinds.

• Event of type $1$: a snail with attributes $a$, $b$ comes and claims that he spent $n$ days climbing the tree. If this message contradicts previously adopted information (i. e. there is no tree for which all previously adopted statements and this one are true), ignore it. Otherwise, adopt it.
• Event of type $2$: a snail with attributes $a$, $b$ comes and asks you how many days he will spend if he climbs the tree. You can only give the answer based on the information you have adopted so far. If you cannot determine the answer precisely, report that.

You need to deal with all the events in order.

蜗牛正在爬一棵树。树的高度为 $h$ 米，蜗牛从位置 $0$ 开始爬行。

每只蜗牛有两个属性 $a$ 和 $b$（满足 $a > b$）。从第 $1$ 天起，一只蜗牛按如下方式爬树：在当天的白天，它向上爬 $a$ 米；在当夜，它休息并下滑 $b$ 米。若在第 $n$ 天，该蜗牛首次到达位置 $h$（即树顶），则它完成爬树过程，此时称该蜗牛共花费了 $n$ 天爬树。注意：在爬树的最后一天，蜗牛不一定恰好向上爬 $a$ 米——若其与树顶的距离小于 $a$，则只需爬完剩余距离即可。

不幸的是，你最初并不知道树的确切高度 $h$，但你知道 $h$ 是一个正整数。接下来将发生 $q$ 个事件，分为两类：

• 类型 $1$ 的事件：一只属性为 $a$、$b$ 的蜗牛到来，并声称它爬树共花费了 $n$ 天。若该声明与此前已采纳的所有信息矛盾（即：不存在任何满足所有已采纳陈述及该新陈述的树高 $h$），则忽略该事件；否则，采纳该陈述。
• 类型 $2$ 的事件：一只属性为 $a$、$b$ 的蜗牛到来，并询问：若它爬这棵树，将花费多少天？你只能依据目前已采纳的信息作答。若无法精确确定答案，则报告无法确定。

你需要按顺序处理全部 $q$ 个事件。

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follows their description.

The first line of each test case contains one integer $q$ ($1\le q \le 2\cdot 10^5$) — the number of events.

For the following $q$ lines, the first integer of each line is either $1$ or $2$, denoting the event type.

If the event type is $1$, then three integers $a$, $b$, and $n$ ($1\le a,b,n \le 10^9$, $a \gt b$) follow.

If the event type is $2$, then two integers $a$ and $b$ ($1\le a,b \le 10^9$, $a \gt b$) follow.

It is guaranteed that the sum of $q$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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 \gt b$）。

若事件类型为 $2$，则随后跟两个整数 $a$ 和 $b$（$1\le a,b \le 10^9$，且 $a \gt b$）。

保证所有测试用例的 $q$ 值之和不超过 $2\cdot 10^5$。

For each test case, output $q$ integers in one line, one for each event, in order. Specifically,

• for each event of type $1$, if you adopt the message, output $1$; if you ignore it, output $0$;
• for each event of type $2$, output an integer denoting the number of days that the snail will spend. If you cannot determine it, output $-1$.

对于每个测试用例，在一行中输出 $q$ 个整数，依次对应每个事件。具体而言：

• 对于每个类型为 $1$ 的事件，若你采纳该消息，则输出 $1$；若忽略该消息，则输出 $0$；
• 对于每个类型为 $2$ 的事件，输出一个整数，表示蜗牛将花费的天数；若无法确定该天数，则输出 $-1$。

In the first test case, we can determine $h=7$ through the first message, so we know the second snail and the third snail need to spend $2$ and $5$ days respectively to reach the top.

Let's show how the second snail climbs:

• During the daylight hours of the $1$st day: climbs up $4$ meters, now at position $4$.
• During the night of the $1$st day: slides down $1$ meters, now at position $3$.
• During the daylight hours of the $2$nd day: climbs up $4$ meters, now at position $7$ (reaches the top).

In the third test case, the second snail's message contradicts the first snail's, because the second snail says he spent $3$ days, and he can climb at most $1+1+2=4$ meters in the first $3$ days. However, the first snail only needs $1$ day to climb $4$ meters.

在第一个测试用例中，我们可以通过第一条消息确定 $h=7$，因此我们知道第二只蜗牛和第三只蜗牛分别需要 $2$ 天和 $5$ 天才能到达顶端。

下面我们展示第二只蜗牛的攀爬过程：

• 第 $1$ 天白天：向上爬 $4$ 米，此时位于位置 $4$。
• 第 $1$ 天夜晚：向下滑 $1$ 米，此时位于位置 $3$。
• 第 $2$ 天白天：向上爬 $4$ 米，此时位于位置 $7$（到达顶端）。

在第三个测试用例中，第二只蜗牛的消息与第一只蜗牛的消息矛盾，因为第二只蜗牛声称自己花费了 $3$ 天，而它在前 $3$ 天最多只能爬升 $1+1+2=4$ 米。然而，第一只蜗牛仅需 $1$ 天就能爬升 $4$ 米。