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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given three arrays $$$a$$$, $$$b$$$ and $$$c$$$. Initially, array $$$a$$$ consists of $$$n$$$ elements, arrays $$$b$$$ and $$$c$$$ are empty.

You are performing the following algorithm that consists of two steps:

- Step $$$1$$$: while $$$a$$$ is not empty, you take the last element from $$$a$$$ and move it in the middle of array $$$b$$$. If $$$b$$$ currently has odd length, you can choose: place the element from $$$a$$$ to the left or to the right of the middle element of $$$b$$$. As a result, $$$a$$$ becomes empty and $$$b$$$ consists of $$$n$$$ elements.
- Step $$$2$$$: while $$$b$$$ is not empty, you take the middle element from $$$b$$$ and move it to the end of array $$$c$$$. If $$$b$$$ currently has even length, you can choose which of two middle elements to take. As a result, $$$b$$$ becomes empty and $$$c$$$ now consists of $$$n$$$ elements.

Can you make array $$$c$$$ sorted in non-decreasing order?

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

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

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

It's guaranteed that the sum of $$$n$$$ doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test, print YES (case-insensitive), if you can make array $$$c$$$ sorted in non-decreasing order. Otherwise, print NO (case-insensitive).

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

## Note
In the first test case, we can do the following for $$$a = [3, 1, 5, 3]$$$:

Step $$$1$$$: $$$a$$$$$$[3, 1, 5, 3]$$$$$$\Rightarrow$$$$$$[3, 1, 5]$$$$$$\Rightarrow$$$$$$[3, 1]$$$$$$\Rightarrow$$$$$$[3]$$$$$$\Rightarrow$$$$$$[]$$$$$$b$$$$$$[]$$$$$$[\underline{3}]$$$$$$[3, \underline{5}]$$$$$$[3, \underline{1}, 5]$$$$$$[3, \underline{3}, 1, 5]$$$

Step $$$2$$$: $$$b$$$$$$[3, 3, \underline{1}, 5]$$$$$$\Rightarrow$$$$$$[3, \underline{3}, 5]$$$$$$\Rightarrow$$$$$$[\underline{3}, 5]$$$$$$\Rightarrow$$$$$$[\underline{5}]$$$$$$\Rightarrow$$$$$$[]$$$$$$c$$$$$$[]$$$$$$[1]$$$$$$[1, 3]$$$$$$[1, 3, 3]$$$$$$[1, 3, 3, 5]$$$ As a result, array $$$c = [1, 3, 3, 5]$$$ and it's sorted.

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
Your friend Ivan asked you to help him rearrange his desktop. The desktop can be represented as a rectangle matrix of size $$$n \times m$$$ consisting of characters '.' (empty cell of the desktop) and '*' (an icon).

The desktop is called good if all its icons are occupying some prefix of full columns and, possibly, the prefix of the next column (and there are no icons outside this figure). In other words, some amount of first columns will be filled with icons and, possibly, some amount of first cells of the next (after the last full column) column will be also filled with icons (and all the icons on the desktop belong to this figure). This is pretty much the same as the real life icons arrangement.

In one move, you can take one icon and move it to any empty cell in the desktop.

Ivan loves to add some icons to his desktop and remove them from it, so he is asking you to answer $$$q$$$ queries: what is the minimum number of moves required to make the desktop good after adding/removing one icon?

Note that queries are permanent and change the state of the desktop.

## Input Format
The first line of the input contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n, m \le 1000; 1 \le q \le 2 \cdot 10^5$$$) — the number of rows in the desktop, the number of columns in the desktop and the number of queries, respectively.

The next $$$n$$$ lines contain the description of the desktop. The $$$i$$$-th of them contains $$$m$$$ characters '.' and '*' — the description of the $$$i$$$-th row of the desktop.

The next $$$q$$$ lines describe queries. The $$$i$$$-th of them contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le n; 1 \le y_i \le m$$$) — the position of the cell which changes its state (if this cell contained the icon before, then this icon is removed, otherwise an icon appears in this cell).

## Output Format
Print $$$q$$$ integers. The $$$i$$$-th of them should be the minimum number of moves required to make the desktop good after applying the first $$$i$$$ queries.

## Examples
```input
4 4 8
..**
.*..
*...
...*
1 3
2 3
3 1
2 3
3 4
4 3
2 3
2 2
```
```output
3
4
4
3
4
5
5
5
```
-----
```input
2 5 5
*...*
*****
1 3
2 2
1 3
1 5
2 3
```
```output
2
3
3
3
2
```

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
Monocarp has just learned a new card trick, and can't wait to present it to you. He shows you the entire deck of $$$n$$$ cards. You see that the values of cards from the topmost to the bottommost are integers $$$a_1, a_2, \dots, a_n$$$, and all values are different.

Then he asks you to shuffle the deck $$$m$$$ times. With the $$$j$$$-th shuffle, you should take $$$b_j$$$ topmost cards and move them under the remaining $$$(n - b_j)$$$ cards without changing the order.

And then, using some magic, Monocarp tells you the topmost card of the deck. However, you are not really buying that magic. You tell him that you know the topmost card yourself. Can you surprise Monocarp and tell him the topmost card before he shows it?

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

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of cards in the deck.

The second line contains $$$n$$$ pairwise distinct integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the values of the cards.

The third line contains a single integer $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — the number of shuffles.

The fourth line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_j \le n - 1$$$) — the amount of cards that are moved on the $$$j$$$-th shuffle.

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$. The sum of $$$m$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print a single integer — the value of the card on the top of the deck after the deck is shuffled $$$m$$$ times.

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

## Note
In the first testcase, each shuffle effectively swaps two cards. After three swaps, the deck will be $$$[2, 1]$$$.

In the second testcase, the second shuffle cancels what the first shuffle did. First, three topmost cards went underneath the last card, then that card went back below the remaining three cards. So the deck remained unchanged from the initial one — the topmost card has value $$$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 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 two arrays $$$a$$$ and $$$b$$$, both consisting of $$$n$$$ integers.

In one move, you can choose two indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$; $$$i \neq j$$$) and swap $$$a_i$$$ with $$$a_j$$$ and $$$b_i$$$ with $$$b_j$$$. You have to perform the swap in both arrays.

You are allowed to perform at most $$$10^4$$$ moves (possibly, zero). Can you make both arrays sorted in a non-decreasing order at the end? If you can, print any sequence of moves that makes both arrays sorted.

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

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — the number of elements in both arrays.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the first array.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$) — the second array.

## Output Format
For each testcase, print the answer. If it's impossible to make both arrays sorted in a non-decreasing order in at most $$$10^4$$$ moves, print -1. Otherwise, first, print the number of moves $$$k$$$ $$$(0 \le k \le 10^4)$$$. Then print $$$i$$$ and $$$j$$$ for each move $$$(1 \le i, j \le n$$$; $$$i \neq j)$$$.

If there are multiple answers, then print any of them. You don't have to minimize the number of moves.

## Examples
```input
3
2
1 2
1 2
2
2 1
1 2
4
2 3 1 2
2 3 2 3
```
```output
0
-1
3
3 1
3 2
4 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 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 two integer numbers, $$$n$$$ and $$$x$$$. You may perform several operations with the integer $$$x$$$.

Each operation you perform is the following one: choose any digit $$$y$$$ that occurs in the decimal representation of $$$x$$$ at least once, and replace $$$x$$$ by $$$x \cdot y$$$.

You want to make the length of decimal representation of $$$x$$$ (without leading zeroes) equal to $$$n$$$. What is the minimum number of operations required to do that?

## Input Format
The only line of the input contains two integers $$$n$$$ and $$$x$$$ ($$$2 \le n \le 19$$$; $$$1 \le x < 10^{n-1}$$$).

## Output Format
Print one integer — the minimum number of operations required to make the length of decimal representation of $$$x$$$ (without leading zeroes) equal to $$$n$$$, or $$$-1$$$ if it is impossible.

## Examples
```input
2 1
```
```output
-1
```
-----
```input
3 2
```
```output
4
```
-----
```input
13 42
```
```output
12
```

## Note
In the second example, the following sequence of operations achieves the goal:

1. multiply $$$x$$$ by $$$2$$$, so $$$x = 2 \cdot 2 = 4$$$;
2. multiply $$$x$$$ by $$$4$$$, so $$$x = 4 \cdot 4 = 16$$$;
3. multiply $$$x$$$ by $$$6$$$, so $$$x = 16 \cdot 6 = 96$$$;
4. multiply $$$x$$$ by $$$9$$$, so $$$x = 96 \cdot 9 = 864$$$.

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: 6.0 seconds
Memory limit: 1024.0 MB

# Problem
You are given a tree, consisting of $$$n$$$ vertices. Each edge has an integer value written on it.

Let $$$f(v, u)$$$ be the number of values that appear exactly once on the edges of a simple path between vertices $$$v$$$ and $$$u$$$.

Calculate the sum of $$$f(v, u)$$$ over all pairs of vertices $$$v$$$ and $$$u$$$ such that $$$1 \le v < u \le n$$$.

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

Each of the next $$$n-1$$$ lines contains three integers $$$v, u$$$ and $$$x$$$ ($$$1 \le v, u, x \le n$$$) — the description of an edge: the vertices it connects and the value written on it.

The given edges form a tree.

## Output Format
Print a single integer — the sum of $$$f(v, u)$$$ over all pairs of vertices $$$v$$$ and $$$u$$$ such that $$$v < u$$$.

## Examples
```input
3
1 2 1
1 3 2
```
```output
4
```
-----
```input
3
1 2 2
1 3 2
```
```output
2
```
-----
```input
5
1 4 4
1 2 3
3 4 4
4 5 5
```
```output
14
```
-----
```input
2
2 1 1
```
```output
1
```
-----
```input
10
10 2 3
3 8 8
4 8 9
5 8 5
3 10 7
7 8 2
5 6 6
9 3 4
1 6 3
```
```output
120
```

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
It turns out that this is exactly the $$$100$$$-th problem of mine that appears in some programming competition. So it has to be special! And what can be more special than another problem about LIS...

You are given a permutation $$$p_1, p_2, \ldots, p_{2n+1}$$$ of integers from $$$1$$$ to $$$2n+1$$$. You will have to process $$$q$$$ updates, where the $$$i$$$-th update consists in swapping $$$p_{u_i}, p_{v_i}$$$.

After each update, find any cyclic shift of $$$p$$$ with $$$LIS \le n$$$, or determine that there is no such shift. (Refer to the output section for details).

Here $$$LIS(a)$$$ denotes the length of longest strictly increasing subsequence of $$$a$$$.

Hacks are disabled in this problem. Don't ask why.

## Input Format
The first line of the input contains two integers $$$n, q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le q \le 10^5$$$).

The second line of the input contains $$$2n+1$$$ integers $$$p_1, p_2, \ldots, p_{2n+1}$$$ ($$$1 \le p_i \le 2n+1$$$, all $$$p_i$$$ are distinct)  — the elements of $$$p$$$.

The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le 2n+1$$$, $$$u_i \neq v_i$$$)  — indicating that you have to swap elements $$$p_{u_i}, p_{v_i}$$$ in the $$$i$$$-th update.

## Output Format
After each update, output any $$$k$$$ $$$(0 \le k \le 2n)$$$, such that the length of the longest increasing subsequence of $$$(p_{k+1}, p_{k+2}, \ldots, p_{2n+1}, p_1, \ldots, p_k)$$$ doesn't exceed $$$n$$$, or $$$-1$$$, if there is no such $$$k$$$.

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

## Note
After the first update, our permutation becomes $$$(5, 2, 3, 4, 1)$$$. We can show that all its cyclic shifts have $$$LIS \ge 3$$$.

After the second update, our permutation becomes $$$(1, 2, 3, 4, 5)$$$. We can show that all its cyclic shifts have $$$LIS \ge 3$$$.

After the third update, our permutation becomes $$$(1, 2, 3, 5, 4)$$$. Its shift by $$$2$$$ is $$$(3, 5, 4, 1, 2)$$$, and its $$$LIS = 2$$$.

After the fourth update, our permutation becomes $$$(1, 2, 3, 4, 5)$$$. We can show that all its cyclic shifts have $$$LIS \ge 3$$$.

After the fifth update, our permutation becomes $$$(4, 2, 3, 1, 5)$$$. Its shift by $$$4$$$ is $$$(5, 4, 2, 3, 1)$$$, and its $$$LIS = 2$$$.

After the fifth update, our permutation becomes $$$(4, 5, 3, 1, 2)$$$. Its shift by $$$0$$$ is $$$(4, 5, 3, 1, 2)$$$, and its $$$LIS = 2$$$.

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 a positive integer $$$n$$$. Your task is to find any three integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$0 \le a, b, c \le 10^9$$$) for which $$$(a\oplus b)+(b\oplus c)+(a\oplus c)=n$$$, or determine that there are no such integers.

Here $$$a \oplus b$$$ denotes the bitwise XOR of $$$a$$$ and $$$b$$$. For example, $$$2 \oplus 4 = 6$$$ and $$$3 \oplus 1=2$$$.

## Input Format
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. The following lines contain the descriptions of the test cases.

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

## Output Format
For each test case, print any three integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$0 \le a, b, c \le 10^9$$$) for which $$$(a\oplus b)+(b\oplus c)+(a\oplus c)=n$$$. If no such integers exist, print $$$-1$$$.

## Examples
```input
5
4
1
12
2046
194723326
```
```output
3 3 1
-1
2 4 6
69 420 666
12345678 87654321 100000000
```

## Note
In the first test case, $$$a=3$$$, $$$b=3$$$, $$$c=1$$$, so $$$(3 \oplus 3)+(3 \oplus 1) + (3 \oplus 1)=0+2+2=4$$$.

In the second test case, there are no solutions.

In the third test case, $$$(2 \oplus 4)+(4 \oplus 6) + (2 \oplus 6)=6+2+4=12$$$.

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 two even integers $$$n$$$ and $$$m$$$. Your task is to find any binary matrix $$$a$$$ with $$$n$$$ rows and $$$m$$$ columns where every cell $$$(i,j)$$$ has exactly two neighbours with a different value than $$$a_{i,j}$$$.

Two cells in the matrix are considered neighbours if and only if they share a side. More formally, the neighbours of cell $$$(x,y)$$$ are: $$$(x-1,y)$$$, $$$(x,y+1)$$$, $$$(x+1,y)$$$ and $$$(x,y-1)$$$.

It can be proven that under the given constraints, an answer always exists.

## Input Format
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The following lines contain the descriptions of the test cases.

The only line of each test case contains two even integers $$$n$$$ and $$$m$$$ ($$$2 \le n,m \le 50$$$) — the height and width of the binary matrix, respectively.

## Output Format
For each test case, print $$$n$$$ lines, each of which contains $$$m$$$ numbers, equal to $$$0$$$ or $$$1$$$ — any binary matrix which satisfies the constraints described in the statement.

It can be proven that under the given constraints, an answer always exists.

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

## Note
White means $$$0$$$, black means $$$1$$$.

The binary matrix from the first test caseThe binary matrix from the second test caseThe binary matrix from the third test case

Now solve the problem and return the code.