410466: GYM104023 K I Wanna Maker
Description
Redcrown the Bear is a gamer who likes playing hardcore games such as I Wanna series. As an experienced player, he has also made many I Wanna levels by himself.
Redcrown is making a new level with a puzzle: given $$$\tilde{k},\tilde{x}$$$ and several consecutive positive integers from $$$l$$$ to $$$r$$$, the player needs to determine whether there exist $$$\tilde{k}$$$ different integers such that their sum is $$$\tilde{x}$$$. Now Redcrown needs to decide the range of the given integers in this level, denoted by the interval $$$[l,r]$$$. In addition to $$$0 < l \le r$$$, he wants to make the interval satisfy $$$n$$$ conditions, each of which is of one of the following two types:
- 1 k x: there exist $$$k$$$ different integers within the interval $$$[l,r]$$$ such that their sum is $$$x$$$.
- 2 k x: there do not exist $$$k$$$ different integers within the interval $$$[l,r]$$$ such that their sum is $$$x$$$. (There are two possible cases: there are less than $$$k$$$ integers in this interval; or, there are $$$k$$$ or more integers in this interval, but there are no $$$k$$$ integers whose sum is $$$x$$$.)
Redcrown wants to know the number of different intervals $$$[l,r]$$$ that satisfy the conditions.
InputThe first line contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$), indicating the number of test cases.
The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), indicating the number of conditions.
Each of the following $$$n$$$ lines contains three integers $$$t,k,x$$$ ($$$1 \le t \le 2$$$, $$$1 \le k \le 10^9$$$, $$$1 \le x \le 10^{9}$$$), indicating a condition.
It is guaranteed that $$$\sum n \le 10^5$$$ over all test cases.
OutputFor each test case, output an integer in a single line indicating the number of different intervals that satisfy the conditions. If there are an infinite number of intervals, output $$$-1$$$ in a single line.
ExampleInput4 2 1 1 2 2 1 4 2 1 1 4 2 1 2 2 1 1 1 2 1 1 4 2 1 15 1 5 20 1 3 8 2 2 25Output
4 -1 0 7Note
For the first test case of the sample, there are two conditions:
- There exists an integer $$$2$$$ within the interval.
- There does not exist an integer $$$4$$$ within the interval.
There are four intervals that satisfy the conditions: $$$[1,2]$$$, $$$[1,3]$$$, $$$[2,2]$$$ and $$$[2,3]$$$.
For the second test case of the sample, there are two conditions:
- There exists an integer $$$4$$$ within the interval.
- There does not exist an integer $$$2$$$ within the interval.
All intervals with $$$3 \le l \le 4$$$ and $$$r \ge 4$$$ satisfy the conditions, so there are an infinite number of intervals.
$$$\quad$$$
Here is a reference picture of the I Wanna level: