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

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 512.0 MB

# Problem
Nezzar has $$$n$$$ balls, numbered with integers $$$1, 2, \ldots, n$$$. Numbers $$$a_1, a_2, \ldots, a_n$$$ are written on them, respectively. Numbers on those balls form a non-decreasing sequence, which means that $$$a_i \leq a_{i+1}$$$ for all $$$1 \leq i < n$$$.

Nezzar wants to color the balls using the minimum number of colors, such that the following holds.

- For any color, numbers on balls will form a strictly increasing sequence if he keeps balls with this chosen color and discards all other balls.

Note that a sequence with the length at most $$$1$$$ is considered as a strictly increasing sequence.

Please help Nezzar determine the minimum number of colors.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$). It is guaranteed that $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$.

## Output Format
For each test case, output the minimum number of colors Nezzar can use.

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

## Note
Let's match each color with some numbers. Then:

In the first test case, one optimal color assignment is $$$[1,2,3,3,2,1]$$$.

In the second test case, one optimal color assignment is $$$[1,2,1,2,1]$$$.

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

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 512.0 MB

# Problem
Nezzar's favorite digit among $$$1,\ldots,9$$$ is $$$d$$$. He calls a positive integer lucky if $$$d$$$ occurs at least once in its decimal representation.

Given $$$q$$$ integers $$$a_1,a_2,\ldots,a_q$$$, for each $$$1 \le i \le q$$$ Nezzar would like to know if $$$a_i$$$ can be equal to a sum of several (one or more) lucky numbers.

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

The first line of each test case contains two integers $$$q$$$ and $$$d$$$ ($$$1 \le q \le 10^4$$$, $$$1 \le d \le 9$$$).

The second line of each test case contains $$$q$$$ integers $$$a_1,a_2,\ldots,a_q$$$ ($$$1 \le a_i \le 10^9$$$).

## Output Format
For each integer in each test case, print "YES" in a single line if $$$a_i$$$ can be equal to a sum of lucky numbers. Otherwise, print "NO".

You can print letters in any case (upper or lower).

## Examples
```input
2
3 7
24 25 27
10 7
51 52 53 54 55 56 57 58 59 60
```
```output
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
```

## Note
In the first test case, $$$24 = 17 + 7$$$, $$$27$$$ itself is a lucky number, $$$25$$$ cannot be equal to a sum of lucky numbers.

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

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Long time ago there was a symmetric array $$$a_1,a_2,\ldots,a_{2n}$$$ consisting of $$$2n$$$ distinct integers. Array $$$a_1,a_2,\ldots,a_{2n}$$$ is called symmetric if for each integer $$$1 \le i \le 2n$$$, there exists an integer $$$1 \le j \le 2n$$$ such that $$$a_i = -a_j$$$.

For each integer $$$1 \le i \le 2n$$$, Nezzar wrote down an integer $$$d_i$$$ equal to the sum of absolute differences from $$$a_i$$$ to all integers in $$$a$$$, i. e. $$$d_i = \sum_{j = 1}^{2n} {|a_i - a_j|}$$$.

Now a million years has passed and Nezzar can barely remember the array $$$d$$$ and totally forget $$$a$$$. Nezzar wonders if there exists any symmetric array $$$a$$$ consisting of $$$2n$$$ distinct integers that generates the array $$$d$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line of each test case contains $$$2n$$$ integers $$$d_1, d_2, \ldots, d_{2n}$$$ ($$$0 \le d_i \le 10^{12}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, print "YES" in a single line if there exists a possible array $$$a$$$. Otherwise, print "NO".

You can print letters in any case (upper or lower).

## Examples
```input
6
2
8 12 8 12
2
7 7 9 11
2
7 11 7 11
1
1 1
4
40 56 48 40 80 56 80 48
6
240 154 210 162 174 154 186 240 174 186 162 210
```
```output
YES
NO
NO
NO
NO
YES
```

## Note
In the first test case, $$$a=[1,-3,-1,3]$$$ is one possible symmetric array that generates the array $$$d=[8,12,8,12]$$$.

In the second test case, it can be shown that there is no symmetric array consisting of distinct integers that can generate array $$$d$$$.

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

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ integers. Initially all elements of $$$a$$$ are either $$$0$$$ or $$$1$$$. You need to process $$$q$$$ queries of two kinds:

- 1 x : Assign to $$$a_x$$$ the value $$$1 - a_x$$$.
- 2 k : Print the $$$k$$$-th largest value of the array.

As a reminder, $$$k$$$-th largest value of the array $$$b$$$ is defined as following:

- Sort the array in the non-increasing order, return $$$k$$$-th element from it.

For example, the second largest element in array $$$[0, 1, 0, 1]$$$ is $$$1$$$, as after sorting in non-increasing order it becomes $$$[1, 1, 0, 0]$$$, and the second element in this array is equal to $$$1$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^5$$$) — the length of the given array and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$) — elements of the initial array.

Each of the following $$$q$$$ lines contains two integers. The first integer is $$$t$$$ ($$$1 \le t \le 2$$$) — the type of query.

- If $$$t = 1$$$ the second integer is $$$x$$$ ($$$1 \le x \le n$$$) — the position of the modified number. You have to assign to $$$a_x$$$ the value $$$1 - a_x$$$.
- If $$$t = 2$$$ the second integer is $$$k$$$ ($$$1 \le k \le n$$$) — you need to print the $$$k$$$-th largest value of the array.

It's guaranteed that there will be at least one query of the second type (satisfying $$$t = 2$$$).

## Output Format
For each query of the second type, print a single integer — the answer to the query.

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

## Note
Initially $$$a = [1, 1, 0, 1, 0]$$$.

The first operation is printing the third largest value, which is $$$1$$$.

The second operation is assigning $$$a_2$$$ the value $$$0$$$, $$$a$$$ becomes $$$[1, 0, 0, 1, 0]$$$.

The third operation is printing the third largest value, it is $$$0$$$.

The fourth operation is printing the first largest value, it is $$$1$$$.

The last operation is printing the fifth largest value, it is $$$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 python3.

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:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
There is a new attraction in Singapore Zoo: The Infinite Zoo.

The Infinite Zoo can be represented by a graph with an infinite number of vertices labeled $$$1,2,3,\ldots$$$. There is a directed edge from vertex $$$u$$$ to vertex $$$u+v$$$ if and only if $$$u\&v=v$$$, where $$$\&$$$ denotes the bitwise AND operation. There are no other edges in the graph.

Zookeeper has $$$q$$$ queries. In the $$$i$$$-th query she will ask you if she can travel from vertex $$$u_i$$$ to vertex $$$v_i$$$ by going through directed edges.

## Input Format
The first line contains an integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — the number of queries.

The $$$i$$$-th of the next $$$q$$$ lines will contain two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i < 2^{30}$$$) — a query made by Zookeeper.

## Output Format
For the $$$i$$$-th of the $$$q$$$ queries, output "YES" in a single line if Zookeeper can travel from vertex $$$u_i$$$ to vertex $$$v_i$$$. Otherwise, output "NO".

You can print your answer in any case. For example, if the answer is "YES", then the output "Yes" or "yeS" will also be considered as correct answer.

## Examples
```input
5
1 4
3 6
1 6
6 2
5 5
```
```output
YES
YES
NO
NO
YES
```

## Note
The subgraph on vertices $$$1,2,3,4,5,6$$$ 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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Let $$$F_k$$$ denote the $$$k$$$-th term of Fibonacci sequence, defined as below:

- $$$F_0 = F_1 = 1$$$
- for any integer $$$n \geq 0$$$, $$$F_{n+2} = F_{n+1} + F_n$$$

You are given a tree with $$$n$$$ vertices. Recall that a tree is a connected undirected graph without cycles.

We call a tree a Fib-tree, if its number of vertices equals $$$F_k$$$ for some $$$k$$$, and at least one of the following conditions holds:

- The tree consists of only $$$1$$$ vertex;
- You can divide it into two Fib-trees by removing some edge of the tree.

Determine whether the given tree is a Fib-tree or not.

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of vertices in the tree.

Then $$$n-1$$$ lines follow, each of which contains two integers $$$u$$$ and $$$v$$$ ($$$1\leq u,v \leq n$$$, $$$u \neq v$$$), representing an edge between vertices $$$u$$$ and $$$v$$$. It's guaranteed that given edges form a tree.

## Output Format
Print "YES" if the given tree is a Fib-tree, or "NO" otherwise.

You can print your answer in any case. For example, if the answer is "YES", then the output "Yes" or "yeS" will also be considered as correct answer.

## Examples
```input
3
1 2
2 3
```
```output
YES
```
-----
```input
5
1 2
1 3
1 4
1 5
```
```output
NO
```
-----
```input
5
1 3
1 2
4 5
3 4
```
```output
YES
```

## Note
In the first sample, we can cut the edge $$$(1, 2)$$$, and the tree will be split into $$$2$$$ trees of sizes $$$1$$$ and $$$2$$$ correspondently. Any tree of size $$$2$$$ is a Fib-tree, as it can be split into $$$2$$$ trees of size $$$1$$$.

In the second sample, no matter what edge we cut, the tree will be split into $$$2$$$ trees of sizes $$$1$$$ and $$$4$$$. As $$$4$$$ isn't $$$F_k$$$ for any $$$k$$$, it's not Fib-tree.

In the third sample, here is one possible order of cutting the edges so that all the trees in the process are Fib-trees: $$$(1, 3), (1, 2), (4, 5), (3, 4)$$$.

Now solve the problem and return the code.