apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array of $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$, and a set $$$b$$$ of $$$k$$$ distinct integers from $$$1$$$ to $$$n$$$.

In one operation, you may choose two integers $$$i$$$ and $$$x$$$ ($$$1 \le i \le n$$$, $$$x$$$ can be any integer) and assign $$$a_i := x$$$. This operation can be done only if $$$i$$$ does not belong to the set $$$b$$$.

Calculate the minimum number of operations you should perform so the array $$$a$$$ is increasing (that is, $$$a_1 < a_2 < a_3 < \dots < a_n$$$), or report that it is impossible.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 5 \cdot 10^5$$$, $$$0 \le k \le n$$$) — the size of the array $$$a$$$ and the set $$$b$$$, respectively.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Then, if $$$k \ne 0$$$, the third line follows, containing $$$k$$$ integers $$$b_1$$$, $$$b_2$$$, ..., $$$b_k$$$ ($$$1 \le b_1 < b_2 < \dots < b_k \le n$$$). If $$$k = 0$$$, this line is skipped.

## Output Format
If it is impossible to make the array $$$a$$$ increasing using the given operations, print $$$-1$$$.

Otherwise, print one integer — the minimum number of operations you have to perform.

## Examples
```input
7 2
1 2 1 1 3 5 1
3 5
```
```output
4
```
-----
```input
3 3
1 3 2
1 2 3
```
```output
-1
```
-----
```input
5 0
4 3 1 2 3
```
```output
2
```
-----
```input
10 3
1 3 5 6 12 9 8 10 13 15
2 4 9
```
```output
3
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 1024.0 MB

# Problem
$$$n$$$ fishermen have just returned from a fishing vacation. The $$$i$$$-th fisherman has caught a fish of weight $$$a_i$$$.

Fishermen are going to show off the fish they caught to each other. To do so, they firstly choose an order in which they show their fish (each fisherman shows his fish exactly once, so, formally, the order of showing fish is a permutation of integers from $$$1$$$ to $$$n$$$). Then they show the fish they caught according to the chosen order. When a fisherman shows his fish, he might either become happy, become sad, or stay content.

Suppose a fisherman shows a fish of weight $$$x$$$, and the maximum weight of a previously shown fish is $$$y$$$ ($$$y = 0$$$ if that fisherman is the first to show his fish). Then:

- if $$$x \ge 2y$$$, the fisherman becomes happy;
- if $$$2x \le y$$$, the fisherman becomes sad;
- if none of these two conditions is met, the fisherman stays content.

Let's call an order in which the fishermen show their fish emotional if, after all fishermen show their fish according to this order, each fisherman becomes either happy or sad. Calculate the number of emotional orders modulo $$$998244353$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 5000$$$).

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$).

## Output Format
Print one integer — the number of emotional orders, taken modulo $$$998244353$$$.

## Examples
```input
4
1 1 4 9
```
```output
20
```
-----
```input
4
4 3 2 1
```
```output
0
```
-----
```input
3
4 2 1
```
```output
6
```
-----
```input
8
42 1337 13 37 420 666 616 97
```
```output
19200
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let's define a function $$$f(x)$$$ ($$$x$$$ is a positive integer) as follows: write all digits of the decimal representation of $$$x$$$ backwards, then get rid of the leading zeroes. For example, $$$f(321) = 123$$$, $$$f(120) = 21$$$, $$$f(1000000) = 1$$$, $$$f(111) = 111$$$.

Let's define another function $$$g(x) = \dfrac{x}{f(f(x))}$$$ ($$$x$$$ is a positive integer as well).

Your task is the following: for the given positive integer $$$n$$$, calculate the number of different values of $$$g(x)$$$ among all numbers $$$x$$$ such that $$$1 \le x \le n$$$.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

Each test case consists of one line containing one integer $$$n$$$ ($$$1 \le n < 10^{100}$$$). This integer is given without leading zeroes.

## Output Format
For each test case, print one integer — the number of different values of the function $$$g(x)$$$, if $$$x$$$ can be any integer from $$$[1, n]$$$.

## Examples
```input
5
4
37
998244353
1000000007
12345678901337426966631415
```
```output
1
2
9
10
26
```

## Note
Explanations for the two first test cases of the example:

1. if $$$n = 4$$$, then for every integer $$$x$$$ such that $$$1 \le x \le n$$$, $$$\dfrac{x}{f(f(x))} = 1$$$;
2. if $$$n = 37$$$, then for some integers $$$x$$$ such that $$$1 \le x \le n$$$, $$$\dfrac{x}{f(f(x))} = 1$$$ (for example, if $$$x = 23$$$, $$$f(f(x)) = 23$$$,$$$\dfrac{x}{f(f(x))} = 1$$$); and for other values of $$$x$$$, $$$\dfrac{x}{f(f(x))} = 10$$$ (for example, if $$$x = 30$$$, $$$f(f(x)) = 3$$$, $$$\dfrac{x}{f(f(x))} = 10$$$). So, there are two different values of $$$g(x)$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are standing on the $$$\mathit{OX}$$$-axis at point $$$0$$$ and you want to move to an integer point $$$x > 0$$$.

You can make several jumps. Suppose you're currently at point $$$y$$$ ($$$y$$$ may be negative) and jump for the $$$k$$$-th time. You can:

- either jump to the point $$$y + k$$$
- or jump to the point $$$y - 1$$$.

What is the minimum number of jumps you need to reach the point $$$x$$$?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first and only line of each test case contains the single integer $$$x$$$ ($$$1 \le x \le 10^6$$$) — the destination point.

## Output Format
For each test case, print the single integer — the minimum number of jumps to reach $$$x$$$. It can be proved that we can reach any integer point $$$x$$$.

## Examples
```input
5
1
2
3
4
5
```
```output
1
3
2
3
4
```

## Note
In the first test case $$$x = 1$$$, so you need only one jump: the $$$1$$$-st jump from $$$0$$$ to $$$0 + 1 = 1$$$.

In the second test case $$$x = 2$$$. You need at least three jumps:

- the $$$1$$$-st jump from $$$0$$$ to $$$0 + 1 = 1$$$;
- the $$$2$$$-nd jump from $$$1$$$ to $$$1 + 2 = 3$$$;
- the $$$3$$$-rd jump from $$$3$$$ to $$$3 - 1 = 2$$$;

Two jumps are not enough because these are the only possible variants:

- the $$$1$$$-st jump as $$$-1$$$ and the $$$2$$$-nd one as $$$-1$$$ — you'll reach $$$0 -1 -1 =-2$$$;
- the $$$1$$$-st jump as $$$-1$$$ and the $$$2$$$-nd one as $$$+2$$$ — you'll reach $$$0 -1 +2 = 1$$$;
- the $$$1$$$-st jump as $$$+1$$$ and the $$$2$$$-nd one as $$$-1$$$ — you'll reach $$$0 +1 -1 = 0$$$;
- the $$$1$$$-st jump as $$$+1$$$ and the $$$2$$$-nd one as $$$+2$$$ — you'll reach $$$0 +1 +2 = 3$$$;

In the third test case, you need two jumps: the $$$1$$$-st one as $$$+1$$$ and the $$$2$$$-nd one as $$$+2$$$, so $$$0 + 1 + 2 = 3$$$.

In the fourth test case, you need three jumps: the $$$1$$$-st one as $$$-1$$$, the $$$2$$$-nd one as $$$+2$$$ and the $$$3$$$-rd one as $$$+3$$$, so $$$0 - 1 + 2 + 3 = 4$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given four different integer points $$$p_1$$$, $$$p_2$$$, $$$p_3$$$ and $$$p_4$$$ on $$$\mathit{XY}$$$ grid.

In one step you can choose one of the points $$$p_i$$$ and move it in one of four directions by one. In other words, if you have chosen point $$$p_i = (x, y)$$$ you can move it to $$$(x, y + 1)$$$, $$$(x, y - 1)$$$, $$$(x + 1, y)$$$ or $$$(x - 1, y)$$$.

Your goal to move points in such a way that they will form a square with sides parallel to $$$\mathit{OX}$$$ and $$$\mathit{OY}$$$ axes (a square with side $$$0$$$ is allowed).

What is the minimum number of steps you need to make such a square?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of four lines. Each line contains two integers $$$x$$$ and $$$y$$$ ($$$0 \le x, y \le 10^9$$$) — coordinates of one of the points $$$p_i = (x, y)$$$.

All points are different in one test case.

## Output Format
For each test case, print the single integer — the minimum number of steps to make a square.

## Examples
```input
3
0 2
4 2
2 0
2 4
1 0
2 0
4 0
6 0
1 6
2 2
2 5
4 1
```
```output
8
7
5
```

## Note
In the first test case, one of the optimal solutions is shown below:

In the second test case, one of the optimal solutions is shown below:

In the third test case, one of the optimal solutions is shown below:

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp is editing a complicated computer program. First, variable $$$x$$$ is declared and assigned to $$$0$$$. Then there are instructions of two types:

1. set $$$y$$$ $$$v$$$ — assign $$$x$$$ a value $$$y$$$ or spend $$$v$$$ burles to remove that instruction (thus, not reassign $$$x$$$);
2. if $$$y$$$ $$$\dots$$$ end block — execute instructions inside the if block if the value of $$$x$$$ is $$$y$$$ and ignore the block otherwise.

if blocks can contain set instructions and other if blocks inside them.

However, when the value of $$$x$$$ gets assigned to $$$s$$$, the computer breaks and immediately catches fire. Polycarp wants to prevent that from happening and spend as few burles as possible.

What is the minimum amount of burles he can spend on removing set instructions to never assign $$$x$$$ to $$$s$$$?

## Input Format
The first line contains two integers $$$n$$$ and $$$s$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le s \le 2 \cdot 10^5$$$) — the number of lines in the program and the forbidden value of $$$x$$$.

The following $$$n$$$ lines describe the program. Each line is one of three types:

1. set $$$y$$$ $$$v$$$ $$$(0 \le y \le 2 \cdot 10^5, 1 \le v \le 10^9)$$$;
2. if $$$y$$$ $$$(0 \le y \le 2 \cdot 10^5)$$$;
3. end.

Each if instruction is matched by an end instruction. Each end instruction has an if instruction to match.

## Output Format
Print a single integer — the minimum amount of burles Polycarp can spend on removing set instructions to never assign $$$x$$$ to $$$s$$$.

## Examples
```input
5 1
set 1 10
set 2 15
if 2
set 1 7
end
```
```output
17
```
-----
```input
7 2
set 3 4
if 3
set 10 4
set 2 7
set 10 1
end
set 4 2
```
```output
4
```
-----
```input
9 200
if 0
set 5 5
if 5
set 100 13
end
if 100
set 200 1
end
end
```
```output
1
```
-----
```input
1 10
set 1 15
```
```output
0
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a tree. We will consider simple paths on it. Let's denote path between vertices $$$a$$$ and $$$b$$$ as $$$(a, b)$$$. Let $$$d$$$-neighborhood of a path be a set of vertices of the tree located at a distance $$$\leq d$$$ from at least one vertex of the path (for example, $$$0$$$-neighborhood of a path is a path itself). Let $$$P$$$ be a multiset of the tree paths. Initially, it is empty. You are asked to maintain the following queries:

- $$$1$$$ $$$u$$$ $$$v$$$ — add path $$$(u, v)$$$ into $$$P$$$ ($$$1 \leq u, v \leq n$$$).
- $$$2$$$ $$$u$$$ $$$v$$$ — delete path $$$(u, v)$$$ from $$$P$$$ ($$$1 \leq u, v \leq n$$$). Notice that $$$(u, v)$$$ equals to $$$(v, u)$$$. For example, if $$$P = \{(1, 2), (1, 2)\}$$$, than after query $$$2$$$ $$$2$$$ $$$1$$$, $$$P = \{(1, 2)\}$$$.
- $$$3$$$ $$$d$$$ — if intersection of all $$$d$$$-neighborhoods of paths from $$$P$$$ is not empty output "Yes", otherwise output "No" ($$$0 \leq d \leq n - 1$$$).

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ — the number of vertices in the tree and the number of queries, accordingly ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$2 \leq q \leq 2 \cdot 10^5$$$).

Each of the following $$$n - 1$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ — indices of vertices connected by $$$i$$$-th edge ($$$1 \le x_i, y_i \le n$$$).

The following $$$q$$$ lines contain queries in the format described in the statement.

It's guaranteed that:

- for a query $$$2$$$ $$$u$$$ $$$v$$$, path $$$(u, v)$$$ (or $$$(v, u)$$$) is present in $$$P$$$,
- for a query $$$3$$$ $$$d$$$, $$$P \neq \varnothing$$$,
- there is at least one query of the third type.

## Output Format
For each query of the third type output answer on a new line.

## Examples
```input
1 4
1 1 1
1 1 1
2 1 1
3 0
```
```output
Yes
```
-----
```input
5 3
1 2
1 3
3 4
4 5
1 1 2
1 5 5
3 1
```
```output
No
```
-----
```input
10 6
1 2
2 3
3 4
4 7
7 10
2 5
5 6
6 8
8 9
1 9 9
1 9 8
1 8 5
3 0
3 1
3 2
```
```output
No
Yes
Yes
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Let's call a sequence $$$b_1, b_2, b_3 \dots, b_{k - 1}, b_k$$$ almost increasing if $$$$$$\min(b_1, b_2) \le \min(b_2, b_3) \le \dots \le \min(b_{k - 1}, b_k).$$$$$$ In particular, any sequence with no more than two elements is almost increasing.

You are given a sequence of integers $$$a_1, a_2, \dots, a_n$$$. Calculate the length of its longest almost increasing subsequence.

You'll be given $$$t$$$ test cases. Solve each test case independently.

Reminder: a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of independent test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — the length of the sequence $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the sequence itself.

It's guaranteed that the total sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.

## Output Format
For each test case, print one integer — the length of the longest almost increasing subsequence.

## Examples
```input
3
8
1 2 7 3 2 1 2 3
2
2 1
7
4 1 5 2 6 3 7
```
```output
6
2
7
```

## Note
In the first test case, one of the optimal answers is subsequence $$$1, 2, 7, 2, 2, 3$$$.

In the second and third test cases, the whole sequence $$$a$$$ is already almost increasing.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Monocarp wants to draw four line segments on a sheet of paper. He wants the $$$i$$$-th segment to have its length equal to $$$a_i$$$ ($$$1 \le i \le 4$$$). These segments can intersect with each other, and each segment should be either horizontal or vertical.

Monocarp wants to draw the segments in such a way that they enclose a rectangular space, and the area of that rectangular space should be maximum possible.

For example, if Monocarp wants to draw four segments with lengths $$$1$$$, $$$2$$$, $$$3$$$ and $$$4$$$, he can do it the following way:

Here, Monocarp has drawn segments $$$AB$$$ (with length $$$1$$$), $$$CD$$$ (with length $$$2$$$), $$$BC$$$ (with length $$$3$$$) and $$$EF$$$ (with length $$$4$$$). He got a rectangle $$$ABCF$$$ with area equal to $$$3$$$ that is enclosed by the segments.

Calculate the maximum area of a rectangle Monocarp can enclose with four segments.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$) — the number of test cases.

Each test case consists of a single line containing four integers $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, $$$a_4$$$ ($$$1 \le a_i \le 10^4$$$) — the lengths of the segments Monocarp wants to draw.

## Output Format
For each test case, print one integer — the maximum area of a rectangle Monocarp can enclose with four segments (it can be shown that the answer is always an integer).

## Examples
```input
4
1 2 3 4
5 5 5 5
3 1 4 1
100 20 20 100
```
```output
3
25
3
2000
```

## Note
The first test case of the example is described in the statement.

For the second test case, Monocarp can draw the segments $$$AB$$$, $$$BC$$$, $$$CD$$$ and $$$DA$$$ as follows:

Here, Monocarp has drawn segments $$$AB$$$ (with length $$$5$$$), $$$BC$$$ (with length $$$5$$$), $$$CD$$$ (with length $$$5$$$) and $$$DA$$$ (with length $$$5$$$). He got a rectangle $$$ABCD$$$ with area equal to $$$25$$$ that is enclosed by the segments.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
There are $$$n$$$ persons located on a plane. The $$$i$$$-th person is located at the point $$$(x_i, y_i)$$$ and initially looks at the point $$$(u_i, v_i)$$$.

At the same moment of time, all persons will start to rotate clockwise synchronously with the same angular speed. They will rotate until they do one full $$$360$$$-degree turn.

It is said that persons $$$A$$$ and $$$B$$$ made eye contact if person $$$A$$$ looks in person $$$B$$$'s direction at the same moment when person $$$B$$$ looks in person $$$A$$$'s direction. If there is a person $$$C$$$ located between persons $$$A$$$ and $$$B$$$, that will not obstruct $$$A$$$ and $$$B$$$ from making eye contact. A person can make eye contact with more than one person at the same time.

Calculate the number of pairs of persons that will make eye contact at least once during the rotation (including the initial moment).

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of persons. The following $$$n$$$ lines describe persons, each line containing four space-separated integers $$$x_i, y_i, u_i, v_i$$$ ($$$|x_i|, |y_i|, |u_i|, |v_i| \le 10^9$$$; $$$x_i \ne u_i$$$ or $$$y_i \ne v_i$$$), where ($$$x_i, y_i$$$) are the coordinates of the point where the $$$i$$$-th person is located and ($$$u_i$$$, $$$v_i$$$) are the coordinates of the point that the $$$i$$$-th person looks at initially. Each person's location is unique in each test case.

The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, print one integer — the number of pairs of persons who will make eye contact at least once during the rotation, including the initial moment.

## Examples
```input
3
2
0 0 0 1
1 0 2 0
3
0 0 1 1
1 1 0 0
1 0 2 0
6
0 0 0 1
1 0 1 2
2 0 2 3
3 0 3 -5
4 0 4 -5
5 0 5 -5
```
```output
0
1
9
```

Now solve the problem and return the code.