310289: CF1810D. Climbing the Tree

D. Climbing the Treetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 > 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.

Input

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>b$) follow.

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

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

Output

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$.

ExampleInput

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

Output

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

Note

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 $ 米，蜗牛从位置 $ 0 $ 开始。
- 每只蜗牛有两个属性 $ a $ 和 $ b $ ($ a > b $)。从第一天开始，一只蜗牛这样爬树：在白天的时段内，它爬上 $ 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 \times 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 \times 10^5 $。

- 输出：
- 对于每个测试用例，输出 $ q $ 个整数，每个事件一个，按顺序。具体来说，
- 对于每个类型 $ 1 $ 的事件，如果你接受该信息，输出 $ 1 $；如果你忽略它，输出 $ 0 $；
- 对于每个类型 $ 2 $ 的事件，输出一个整数，表示蜗牛将花费的天数。如果你无法确定，输出 $ -1 $。

请注意，上述内容是网页内容的翻译，并按照要求以 LaTeX 格式提供了公式。题目大意： - 题目描述了一群蜗牛在爬树。树的高度为 $ h $ 米，蜗牛从位置 $ 0 $ 开始。 - 每只蜗牛有两个属性 $ a $ 和 $ b $ ($ a > b $)。从第一天开始，一只蜗牛这样爬树：在白天的时段内，它爬上 $ 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 \times 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 \times 10^5 $。 - 输出： - 对于每个测试用例，输出 $ q $ 个整数，每个事件一个，按顺序。具体来说， - 对于每个类型 $ 1 $ 的事件，如果你接受该信息，输出 $ 1 $；如果你忽略它，输出 $ 0 $； - 对于每个类型 $ 2 $ 的事件，输出一个整数，表示蜗牛将花费的天数。如果你无法确定，输出 $ -1 $。 请注意，上述内容是网页内容的翻译，并按照要求以 LaTeX 格式提供了公式。