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

# Problem
There is a tree of $$$N$$$ vertices and $$$N-1$$$ edges. The $$$i$$$-th edge connects vertices $$$U_i$$$ and $$$V_i$$$ and has a length of $$$W_i$$$.

Chaneka, the owner of the tree, asks you $$$Q$$$ times. For the $$$j$$$-th question, the following is the question format:

- $$$X_j$$$ $$$K_j$$$ – If each edge that contains vertex $$$X_j$$$ has its length multiplied by $$$K_j$$$, what is the diameter of the tree?

Notes:

- Each of Chaneka's question is independent, which means the changes in edge length do not influence the next questions.
- The diameter of a tree is the maximum possible distance between two different vertices in the tree.

## Input Format
The first line contains a single integer $$$N$$$ ($$$2\leq N\leq10^5$$$) — the number of vertices in the tree.

The $$$i$$$-th of the next $$$N-1$$$ lines contains three integers $$$U_i$$$, $$$V_i$$$, and $$$W_i$$$ ($$$1 \leq U_i,V_i \leq N$$$; $$$1\leq W_i\leq10^9$$$) — an edge that connects vertices $$$U_i$$$ and $$$V_i$$$ with a length of $$$W_i$$$. The edges form a tree.

The $$$(N+1)$$$-th line contains a single integer $$$Q$$$ ($$$1\leq Q\leq10^5$$$) — the number of questions.

The $$$j$$$-th of the next $$$Q$$$ lines contains two integers $$$X_j$$$ and $$$K_j$$$ as described ($$$1 \leq X_j \leq N$$$; $$$1 \leq K_j \leq 10^9$$$).

## Output Format
Output $$$Q$$$ lines with an integer in each line. The integer in the $$$j$$$-th line represents the diameter of the tree on the $$$j$$$-th question.

## Examples
```input
7
5 1 2
1 4 2
3 4 1
2 5 3
6 1 6
4 7 2
2
4 3
3 2
```
```output
18
11
```
-----
```input
3
1 2 1000000000
2 3 1000000000
1
2 1000000000
```
```output
2000000000000000000
```

## Note
In the first example, the following is the tree without any changes.

The following is the tree on the $$$1$$$-st question.

The maximum distance is between vertices $$$6$$$ and $$$7$$$, which is $$$6+6+6=18$$$, so the diameter is $$$18$$$.

The following is the tree on the $$$2$$$-nd question.

The maximum distance is between vertices $$$2$$$ and $$$6$$$, which is $$$3+2+6=11$$$, so the diameter is $$$11$$$.

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
Pak Chanek comes up with an idea in the midst of boredom to play a game. The game is a rock tower game. There is a big rock that is used as a base. There are also $$$N$$$ small identical rocks that Pak Chanek will use to build a rock tower with a height of $$$N$$$ above the base rock.

Initially, there are no small rocks that are located above the base rock. In other words, the height of the tower above the base rock is initially $$$0$$$. In one move, Pak Chanek can place one small rock onto the top of the tower which makes the height of the tower above the base rock increase by $$$1$$$. Each time Pak Chanek place one small rock, the following will happen after the small rock is placed:

- Let's say $$$x$$$ is the height of the tower above the base rock right after the small rock is placed.
- There is a probability of $$$P_x$$$ percent that the topmost rock falls.
- If $$$x \geq 2$$$ and the topmost rock falls, then there is another probability of $$$P_x$$$ percent that the $$$2$$$-nd topmost rock also falls.
- If $$$x \geq 3$$$ and the $$$2$$$-nd topmost rock falls, then there is another probability of $$$P_x$$$ percent that the $$$3$$$-rd topmost rock also falls.
- If $$$x \geq 4$$$ and the $$$3$$$-rd topmost rock falls, then there is another probability of $$$P_x$$$ percent that the $$$4$$$-th topmost rock also falls.
- And so on.

If the tower successfully reaches a height of $$$N$$$ without any rocks falling after that, then the game is ended.

If given an integer array $$$[P_1, P_2, \ldots, P_N]$$$, what is the expected value of the number of moves that Pak Chanek needs to do to end the game? It can be proven that the expected value can be represented as an simple fraction $$$\frac{P}{Q}$$$ where $$$Q$$$ is coprime to $$$998\,244\,353$$$. Output the value of $$$P \times Q^{-1}$$$ modulo $$$998\,244\,353$$$.

## Input Format
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 2\cdot10^5$$$) — the required height of the rock tower.

The second line contains $$$N$$$ integers $$$P_1, P_2, P_3, \ldots, P_N$$$ ($$$0 \leq P_i \leq 99$$$).

## Output Format
An integer representing the expected value of the number of moves that Pak Chanek needs to do to end the game, modulo $$$998\,244\,353$$$.

## Examples
```input
2
80 50
```
```output
499122186
```
-----
```input
3
25 16 20
```
```output
879786027
```

## Note
In the first example, the expected value of the number of moves that Pak Chanek needs to do to end the game is $$$\frac{19}{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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an undirected connected graph in which any two distinct simple cycles do not have common vertices. Since the graph can be very large, it is given to you in a compressed form: for each edge, you are also given a number $$$d$$$, which indicates that there are $$$d$$$ additional vertices on this edge.

You need to assign a weight to each vertex and each edge of the graph — an integer from $$$1$$$ to $$$3$$$.

An edge of the graph is called good if the bitwise XOR of the weights of its adjacent vertices is not equal to $$$0$$$ and not equal to the weight of that edge.

Similarly, a vertex of the graph is called good if the bitwise XOR of the weights of its adjacent edges is not equal to $$$0$$$ and not equal to the weight of that vertex.

You need to determine how many ways there are to assign weights to the vertices and edges of the graph so that all vertices and edges are good. Since the answer can be quite large, you need to calculate the remainder of the answer divided by $$$998\,244\,353$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ — the number of vertices and the number of edges in the graph ($$$2 \le n \le 5 \cdot 10^5$$$, $$$n - 1 \le m \le 10^6$$$).

Each of the next $$$m$$$ lines contains three integers $$$a_i, b_i$$$, and $$$d_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$, $$$0 \le d_i \le 10^9$$$), indicating that there is an edge in the graph connecting vertices $$$a_i$$$ and $$$b_i$$$. Additionally, on this edge, there are $$$d_i$$$ additional vertices. It is guaranteed that the given graph is connected, there are no multiple edges, loops, and any two distinct simple cycles of the graph do not have common vertices.

## Output Format
Output a single integer — the answer to the problem modulo $$$998\,244\,353$$$.

## Examples
```input
3 3
1 2 0
2 3 0
3 1 0
```
```output
12
```
-----
```input
6 7
1 2 0
2 3 0
3 1 0
4 5 0
5 6 0
6 4 0
4 3 0
```
```output
0
```
-----
```input
2 1
2 1 777
```
```output
0
```
-----
```input
3 3
1 2 0
2 3 110850709
3 1 1000000000
```
```output
179179178
```

## Note
In the first test, the graph is a simple cycle of $$$3$$$ vertices. It can be shown, that there are exactly $$$12$$$ ways to assign weights, to make all vertexes and edges good.

In the second test, the graph has the form of two simple cycles of $$$3$$$ vertices connected by an edge. It can be shown that for such a graph there are no ways to arrange weights so that all vertices and edges are good.

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 a string $$$s$$$, consisting only of characters '0' and/or '1'.

In one operation, you choose a position $$$i$$$ from $$$1$$$ to $$$|s| - 1$$$, where $$$|s|$$$ is the current length of string $$$s$$$. Then you insert a character between the $$$i$$$-th and the $$$(i+1)$$$-st characters of $$$s$$$. If $$$s_i = s_{i+1}$$$, you insert '1'. If $$$s_i \neq s_{i+1}$$$, you insert '0'.

Is it possible to make the number of zeroes in the string strictly greater than the number of ones, using any number of operations (possibly, none)?

## 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 an integer $$$n$$$ ($$$1 \le n \le 100$$$).

The second line contains a string $$$s$$$ of length exactly $$$n$$$, consisting only of characters '0' and/or '1'.

## Output Format
For each testcase, print "YES" if it's possible to make the number of zeroes in $$$s$$$ strictly greater than the number of ones, using any number of operations (possibly, none). Otherwise, print "NO".

## Examples
```input
3
2
00
2
11
2
10
```
```output
YES
NO
YES
```

## Note
In the first testcase, the number of zeroes is already greater than the number of ones.

In the second testcase, it's impossible to insert any zeroes in the string.

In the third testcase, you can choose $$$i = 1$$$ to insert a zero between the $$$1$$$-st and the $$$2$$$-nd characters. Since $$$s_1 \neq s_2$$$, you insert a '0'. The resulting string is "100". It has two zeroes and only a single one, so the answer is "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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an integer array $$$a_1, a_2, \dots, a_n$$$, all its elements are distinct.

First, you are asked to insert one more integer $$$a_{n+1}$$$ into this array. $$$a_{n+1}$$$ should not be equal to any of $$$a_1, a_2, \dots, a_n$$$.

Then, you will have to make all elements of the array equal. At the start, you choose a positive integer $$$x$$$ ($$$x > 0$$$). In one operation, you add $$$x$$$ to exactly one element of the array. Note that $$$x$$$ is the same for all operations.

What's the smallest number of operations it can take you to make all elements equal, after you choose $$$a_{n+1}$$$ and $$$x$$$?

## 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$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$). All $$$a_i$$$ are distinct.

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

## Output Format
For each testcase, print a single integer — the smallest number of operations it can take you to make all elements equal, after you choose integers $$$a_{n+1}$$$ and $$$x$$$.

## Examples
```input
3
3
1 2 3
5
1 -19 17 -3 -15
1
10
```
```output
6
27
1
```

## Note
In the first testcase, you can choose $$$a_{n+1} = 4$$$, the array becomes $$$[1, 2, 3, 4]$$$. Then choose $$$x = 1$$$ and apply the operation $$$3$$$ times to the first element, $$$2$$$ times to the second element, $$$1$$$ time to the third element and $$$0$$$ times to the fourth element.

In the second testcase, you can choose $$$a_{n+1} = 13, x = 4$$$.

In the third testcase, you can choose $$$a_{n+1} = 9, x = 1$$$. Then apply the operation once to $$$a_{n+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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$n$$$ strings $$$s_1, s_2, \dots, s_n$$$, consisting of lowercase Latin letters. Let $$$|x|$$$ be the length of string $$$x$$$.

Let a collapse $$$C(a, b)$$$ of two strings $$$a$$$ and $$$b$$$ be the following operation:

- if $$$a$$$ is empty, $$$C(a, b) = b$$$;
- if $$$b$$$ is empty, $$$C(a, b) = a$$$;
- if the last letter of $$$a$$$ is equal to the first letter of $$$b$$$, then $$$C(a, b) = C(a_{1,|a|-1}, b_{2,|b|})$$$, where $$$s_{l,r}$$$ is the substring of $$$s$$$ from the $$$l$$$-th letter to the $$$r$$$-th one;
- otherwise, $$$C(a, b) = a + b$$$, i. e. the concatenation of two strings.

Calculate $$$\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

Each of the next $$$n$$$ lines contains a string $$$s_i$$$ ($$$1 \le |s_i| \le 10^6$$$), consisting of lowercase Latin letters.

The total length of the strings doesn't exceed $$$10^6$$$.

## Output Format
Print a single integer — $$$\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$$$.

## Examples
```input
3
aba
ab
ba
```
```output
20
```
-----
```input
5
abab
babx
xab
xba
bab
```
```output
126
```

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

# Problem
You are playing a word puzzle. The puzzle starts with a $$$3$$$ by $$$3$$$ grid, where each cell contains either the letter A, B, or C.

The goal of this puzzle is to find the lexicographically smallest possible word of length $$$3$$$. The word can be formed by choosing three different cells where the cell containing the first letter is adjacent to the cell containing the second letter, and the cell containing the second letter is adjacent to the cell containing the third letter.

Two cells are adjacent to each other if they share a border or a corner, as shown in the following illustration. Formally, if $$$(r, c)$$$ denotes the cell in the $$$r$$$-th row and $$$c$$$-th column, then cell $$$(r, c)$$$ is adjacent to cell $$$(r, c + 1)$$$, $$$(r - 1, c + 1)$$$, $$$(r - 1, c)$$$, $$$(r - 1, c - 1)$$$, $$$(r, c - 1)$$$, $$$(r + 1, c - 1)$$$, $$$(r + 1, c)$$$, and $$$(r + 1, c + 1)$$$.

Determine the lexicographically smallest possible word of length $$$3$$$ that you can find within the grid.

A string $$$s$$$ of length $$$n$$$ is lexicographically smaller than string $$$t$$$ of the same length if there exists an integer $$$1 \leq i \leq n$$$ such that $$$s_j = t_j$$$ for all $$$1 \leq j < i$$$, and $$$s_i < t_i$$$ in alphabetical order. The following illustration shows some examples on some grids and their the lexicographically smallest possible word of length $$$3$$$ that you can find within the grids.

## Input Format
Input consists of three lines, each containing three letters, representing the puzzle grid. Each letter in the grid can only be either A, B, or C.

## Output Format
Output the lexicographically smallest possible word of length $$$3$$$ that you can find within the grid.

## Examples
```input
BCB
CAC
BCB
```
```output
ABC
```
-----
```input
BCB
CCC
CCA
```
```output
ACB
```
-----
```input
ACA
CBC
ACA
```
```output
ABA
```
-----
```input
ACA
CAC
ACA
```
```output
AAA
```
-----
```input
CCC
CBC
CCC
```
```output
BCC
```

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

# Problem
You are given $$$N$$$ buttons (numbered from $$$1$$$ to $$$N$$$) and $$$N$$$ lamps (numbered from $$$1$$$ to $$$N$$$). Each lamp can either be on or off. Initially, lamp $$$i$$$ is on if $$$A_i = 1$$$, and off if $$$A_i = 0$$$.

Button $$$i$$$ is connected to lamp $$$i - 1$$$ (if $$$i > 1$$$) and lamp $$$i + 1$$$ (if $$$i < N$$$). In one move, you can press a button $$$i$$$ only if lamp $$$i$$$ is on. When a button is pressed, the state of the lamps connected to this button is toggled. Formally, the lamps will be on if it was off previously, and the lamps will be off if it was on previously. Note that lamp $$$i$$$ is not connected to button $$$i$$$, thus, the state of lamp $$$i$$$ does not change if button $$$i$$$ is pressed.

After zero or more moves, you want lamp $$$i$$$ to be on if $$$B_i = 1$$$, and off if $$$B_i = 0$$$. Determine if it is possible to achieve this task.

## Input Format
This problem has multiple test cases. The first line consists of an integer $$$T$$$ ($$$1 \leq T \leq 1000$$$), which represents the number of test cases. Each test case consists of three lines.

The first line of each test case consists of an integer $$$N$$$ ($$$3 \le N \le 200\,000$$$). The sum of $$$N$$$ over all test cases does not exceed $$$200\,000$$$.

The second line of each test case consists of a string $$$A$$$ of length $$$N$$$. Each character of $$$A$$$ can either be 0 or 1. The $$$i$$$-th character represents the initial state of lamp $$$i$$$.

The third line of each test case consists of a string $$$A$$$ of length $$$N$$$. Each character of $$$B$$$ can either be 0 or 1. The $$$i$$$-th character represents the desired final state of lamp $$$i$$$.

## Output Format
For each test case, output YES in a single line if the final state of all lamps can be reached after zero or more moves, or NO otherwise.

## Examples
```input
2
4
0101
0100
3
000
010
```
```output
YES
NO
```
-----
```input
5
7
0101011
1111010
5
11111
00000
4
1101
1101
6
101010
100100
3
000
000
```
```output
NO
NO
YES
YES
YES
```

## Note
Explanation for the sample input/output #1

For the first test case, by pressing the buttons $$$4, 2, 4, 3, 1, 2$$$ in sequence, the condition of the buttons changes as: $$$0101 \rightarrow 0111 \rightarrow 1101 \rightarrow 1111 \rightarrow 1010 \rightarrow 1110 \rightarrow 0100$$$.

For the second test case, you are unable to press any button, hence it is impossible to reach the final state.

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

# Problem
You are currently researching the Merge Sort algorithm. Merge Sort is a sorting algorithm that is based on the principle of Divide and Conquer. It works by dividing an array into two subarrays of equal length, sorting each subarrays, then merging the sorted subarrays back together to form the final sorted array.

You are particularly interested in the merging routine. Common merge implementation will combine two subarrays by iteratively comparing their first elements, and move the smaller one to a new merged array. More precisely, the merge algorithm can be presented by the following pseudocode.

During your research, you are keen to understand the behaviour of the merge algorithm when arrays $$$A$$$ and $$$B$$$ are not necessarily sorted. For example, if $$$A = [3, 1, 6]$$$ and $$$B = [4, 5, 2]$$$, then $$$\text{Merge}(A, B) = [3, 1, 4, 5, 2, 6]$$$.

To further increase the understanding of the merge algorithm, you decided to work on the following problem. You are given an array $$$C$$$ of length $$$2 \cdot N$$$ such that it is a permutation of $$$1$$$ to $$$2 \cdot N$$$. Construct any two arrays $$$A$$$ and $$$B$$$ of the same length $$$N$$$, such that $$$\text{Merge}(A, B) = C$$$, or determine if it is impossible to do so.

## Input Format
The first line consists of an integer $$$N$$$ ($$$1 \leq N \leq 1000$$$).

The following line consists of $$$2 \cdot N$$$ integers $$$C_i$$$. The array $$$C$$$ is a permutation of $$$1$$$ to $$$2 \cdot N$$$.

## Output Format
If it is impossible to construct two arrays $$$A$$$ and $$$B$$$ of length $$$N$$$ such that $$$\text{Merge}(A, B) = C$$$, then output -1.

Otherwise, output the arrays $$$A$$$ and $$$B$$$ in two lines. The first line consists of $$$N$$$ integers $$$A_i$$$. The second line consists of $$$N$$$ integers $$$B_i$$$. If there are several possible answers, output any of them.

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

## Note
Explanation for the sample input/output #1

The solution $$$A = [3, 1, 4]$$$ and $$$B = [5, 2, 6]$$$ is also correct.

Explanation for the sample input/output #2

The solution $$$A = [1, 2, 3, 4]$$$ and $$$B = [5, 6, 7, 8]$$$ is also correct.

Now solve the problem and return the code.