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: 512.0 MB

# Problem
The Berland language consists of words having exactly two letters. Moreover, the first letter of a word is different from the second letter. Any combination of two different Berland letters (which, by the way, are the same as the lowercase letters of Latin alphabet) is a correct word in Berland language.

The Berland dictionary contains all words of this language. The words are listed in a way they are usually ordered in dictionaries. Formally, word $$$a$$$ comes earlier than word $$$b$$$ in the dictionary if one of the following conditions hold:

- the first letter of $$$a$$$ is less than the first letter of $$$b$$$;
- the first letters of $$$a$$$ and $$$b$$$ are the same, and the second letter of $$$a$$$ is less than the second letter of $$$b$$$.

So, the dictionary looks like that:

- Word $$$1$$$: ab
- Word $$$2$$$: ac
- ...
- Word $$$25$$$: az
- Word $$$26$$$: ba
- Word $$$27$$$: bc
- ...
- Word $$$649$$$: zx
- Word $$$650$$$: zy

You are given a word $$$s$$$ from the Berland language. Your task is to find its index in the dictionary.

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

Each test case consists of one line containing $$$s$$$ — a string consisting of exactly two different lowercase Latin letters (i. e. a correct word of the Berland language).

## Output Format
For each test case, print one integer — the index of the word $$$s$$$ in the dictionary.

## Examples
```input
7
ab
ac
az
ba
bc
zx
zy
```
```output
1
2
25
26
27
649
650
```

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 a string $$$s$$$, consisting only of Latin letters 'a', and a string $$$t$$$, consisting of lowercase Latin letters.

In one move, you can replace any letter 'a' in the string $$$s$$$ with a string $$$t$$$. Note that after the replacement string $$$s$$$ might contain letters other than 'a'.

You can perform an arbitrary number of moves (including zero). How many different strings can you obtain? Print the number, or report that it is infinitely large.

Two strings are considered different if they have different length, or they differ at some index.

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

The first line of each testcase contains a non-empty string $$$s$$$, consisting only of Latin letters 'a'. The length of $$$s$$$ doesn't exceed $$$50$$$.

The second line contains a non-empty string $$$t$$$, consisting of lowercase Latin letters. The length of $$$t$$$ doesn't exceed $$$50$$$.

## Output Format
For each testcase, print the number of different strings $$$s$$$ that can be obtained after an arbitrary amount of moves (including zero). If the number is infinitely large, print -1. Otherwise, print the number.

## Examples
```input
3
aaaa
a
aa
abc
a
b
```
```output
1
-1
2
```

## Note
In the first example, you can replace any letter 'a' with the string "a", but that won't change the string. So no matter how many moves you make, you can't obtain a string other than the initial one.

In the second example, you can replace the second letter 'a' with "abc". String $$$s$$$ becomes equal to "aabc". Then the second letter 'a' again. String $$$s$$$ becomes equal to "aabcbc". And so on, generating infinitely many different strings.

In the third example, you can either leave string $$$s$$$ as is, performing zero moves, or replace the only 'a' with "b". String $$$s$$$ becomes equal to "b", so you can't perform more moves on it.

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 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 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: 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 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
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 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 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 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 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 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: 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 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
There is an integer $$$n$$$ without zeros in its decimal representation. Alice and Bob are playing a game with this integer. Alice starts first. They play the game in turns.

On her turn, Alice must swap any two digits of the integer that are on different positions. Bob on his turn always removes the last digit of the integer. The game ends when there is only one digit left.

You have to find the smallest integer Alice can get in the end, if she plays optimally.

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

The first and the only line of each test case contains the integer $$$n$$$ ($$$10 \le n \le 10^9$$$) — the integer for the game. $$$n$$$ does not have zeros in its decimal representation.

## Output Format
For each test case output a single integer — the smallest integer Alice can get in the end of the game.

## Examples
```input
3
12
132
487456398
```
```output
2
1
3
```

## Note
In the first test case Alice has to swap $$$1$$$ and $$$2$$$. After that Bob removes the last digit, $$$1$$$, so the answer is $$$2$$$.

In the second test case Alice can swap $$$3$$$ and $$$1$$$: $$$312$$$. After that Bob deletes the last digit: $$$31$$$. Then Alice swaps $$$3$$$ and $$$1$$$: $$$13$$$ and Bob deletes $$$3$$$, so the answer is $$$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 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 given three positive integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$a < b < c$$$). You have to find three positive integers $$$x$$$, $$$y$$$, $$$z$$$ such that:

$$$$$$x \bmod y = a,$$$$$$ $$$$$$y \bmod z = b,$$$$$$ $$$$$$z \bmod x = c.$$$$$$

Here $$$p \bmod q$$$ denotes the remainder from dividing $$$p$$$ by $$$q$$$. It is possible to show that for such constraints the answer always exists.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases. Description of the test cases follows.

Each test case contains a single line with three integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \le a < b < c \le 10^8$$$).

## Output Format
For each test case output three positive integers $$$x$$$, $$$y$$$, $$$z$$$ ($$$1 \le x, y, z \le 10^{18}$$$) such that $$$x \bmod y = a$$$, $$$y \bmod z = b$$$, $$$z \bmod x = c$$$.

You can output any correct answer.

## Examples
```input
4
1 3 4
127 234 421
2 7 8
59 94 388
```
```output
12 11 4
1063 234 1484
25 23 8
2221 94 2609
```

## Note
In the first test case:

$$$$$$x \bmod y = 12 \bmod 11 = 1;$$$$$$

$$$$$$y \bmod z = 11 \bmod 4 = 3;$$$$$$

$$$$$$z \bmod x = 4 \bmod 12 = 4.$$$$$$

Now solve the problem and return the code.