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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$n$$$ points with integer coordinates $$$x_1,\dots x_n$$$, which lie on a number line.

For some integer $$$s$$$, we construct segments [$$$s,x_1$$$], [$$$s,x_2$$$], $$$\dots$$$, [$$$s,x_n$$$]. Note that if $$$x_i<s$$$, then the segment will look like [$$$x_i,s$$$]. The segment [$$$a, b$$$] covers all integer points $$$a, a+1, a+2, \dots, b$$$.

We define the power of a point $$$p$$$ as the number of segments that intersect the point with coordinate $$$p$$$, denoted as $$$f_p$$$.

Your task is to compute $$$\sum\limits_{p=1}^{10^9}f_p$$$ for each $$$s \in \{x_1,\dots,x_n\}$$$, i.e., the sum of $$$f_p$$$ for all integer points from $$$1$$$ to $$$10^9$$$.

For example, if the initial coordinates are $$$[1,2,5,7,1]$$$ and we choose $$$s=5$$$, then the segments will be: $$$[1,5]$$$,$$$[2,5]$$$,$$$[5,5]$$$,$$$[5,7]$$$,$$$[1,5]$$$. And the powers of the points will be: $$$f_1=2, f_2=3, f_3=3, f_4=3, f_5=5, f_6=1, f_7=1, f_8=0, \dots, f_{10^9}=0$$$. Their sum is $$$2+3+3+3+5+1+1=18$$$.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — the number of points.

The second line contains $$$n$$$ integers $$$x_1,x_2 \dots x_n$$$ ($$$1 \le x_i \le 10^9$$$) — the coordinates of the points.

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

## Output Format
For each test case, output $$$n$$$ integers, where the $$$i$$$-th integer is equal to the sum of the powers of all points for $$$s=x_i$$$.

## Examples
```input
3
3
1 4 3
5
1 2 5 7 1
4
1 10 100 1000
```
```output
8 7 6
16 15 18 24 16
1111 1093 1093 2893
```

## Note
In the first test case we first choose $$$s=x_1=1$$$, then the following segments are formed: $$$[1,1]$$$,$$$[1,4]$$$,$$$[1,3]$$$.

The powers of the points will be as follows: $$$f_1=3, f_2=2, f_3=2, f_4=1, f_5=0 \dots$$$ The sum of powers of the points: $$$3+2+2+1+0+\dots+0=8$$$.

After that we choose $$$s=x_2=4$$$. Then there will be such segments: $$$[1,4]$$$,$$$[4,4]$$$,$$$[3,4]$$$, and powers of the points are $$$f_1=1, f_2=1, f_3=2, f_4=3$$$.

At the end we take $$$s=x_3=3$$$ and the segments look like this: $$$[1,3]$$$,$$$[3,4]$$$,$$$[3,3]$$$, the powers of the points are $$$f_1=1, f_2=1, f_3=3, f_4=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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
You have an array $$$a$$$ of length $$$n$$$.

Your task is to answer $$$q$$$ queries: given $$$x,y$$$, find the number of pairs $$$i$$$ and $$$j$$$ ($$$1 \le i < j \le n$$$) that both $$$a_i + a_j = x$$$ and $$$a_i \cdot a_j = y$$$.

That is, for the array $$$[1,3,2]$$$ and asking for $$$x=3,y=2$$$ the answer is $$$1$$$:

- $$$i=1$$$ and $$$j=2$$$ fail because $$$1 + 3 = 4$$$ and not $$$3,$$$ also $$$1 \cdot 3=3$$$ and not $$$2$$$;
- $$$i=1$$$ and $$$j=3$$$ satisfies both conditions;
- $$$i=2$$$ and $$$j=3$$$ fail because $$$3 + 2 = 5$$$ and not $$$3,$$$ also $$$3 \cdot 2=6$$$ and not $$$2$$$;

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

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

The third line of each test case contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1 \le |a_i| \le 10^9$$$) — array $$$a$$$.

The fourth line of each test case contains the integer $$$q$$$ ($$$1 \le q \le 2\cdot 10^5$$$) — the number of requests.

The next $$$q$$$ lines contain two numbers each $$$x$$$ and $$$y$$$ ($$$1 \le |x|\le 2\cdot 10^9,1\le |y|\le 10^{18}$$$) — request.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$. This is also guaranteed for the sum of $$$q$$$ values.

## Output Format
For each test case print a line with $$$q$$$ numbers — the answers to the queries.

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

## Note
For the first test case, let's analyze each pair of numbers separately:

- pair $$$(a_1,a_2)$$$: $$$a_1 + a_2 = 4$$$, $$$a_1 \cdot a_2 = 3$$$
- pair $$$(a_1,a_3)$$$: $$$a_1 + a_3 = 3$$$, $$$a_1 \cdot a_3 = 2$$$
- pair $$$(a_2,a_3)$$$: $$$a_2 + a_3 = 5$$$, $$$a_2 \cdot a_3 = 6$$$

In the second test case, all combinations of pairs are suitable.

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
Chaneka, Pak Chanek's child, is an ambitious kid, so Pak Chanek gives her the following problem to test her ambition.

Given an array of integers $$$[A_1, A_2, A_3, \ldots, A_N]$$$. In one operation, Chaneka can choose one element, then increase or decrease the element's value by $$$1$$$. Chaneka can do that operation multiple times, even for different elements.

What is the minimum number of operations that must be done to make it such that $$$A_1 \times A_2 \times A_3 \times \ldots \times A_N = 0$$$?

## Input Format
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$).

The second line contains $$$N$$$ integers $$$A_1, A_2, A_3, \ldots, A_N$$$ ($$$-10^5 \leq A_i \leq 10^5$$$).

## Output Format
An integer representing the minimum number of operations that must be done to make it such that $$$A_1 \times A_2 \times A_3 \times \ldots \times A_N = 0$$$.

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

## Note
In the first example, initially, $$$A_1\times A_2\times A_3=2\times(-6)\times5=-60$$$. Chaneka can do the following sequence of operations:

1. Decrease the value of $$$A_1$$$ by $$$1$$$. Then, $$$A_1\times A_2\times A_3=1\times(-6)\times5=-30$$$
2. Decrease the value of $$$A_1$$$ by $$$1$$$. Then, $$$A_1\times A_2\times A_3=0\times(-6)\times5=0$$$

In the third example, Chaneka does not have to do any operations, because from the start, it already holds that $$$A_1\times A_2\times A_3\times A_4\times A_5=0\times(-1)\times0\times1\times0=0$$$

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

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

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

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Pak Chanek observes that the carriages of a train is always full on morning departure hours and afternoon departure hours. Therefore, the balance between carriages is needed so that it is not too crowded in only a few carriages.

A train contains $$$N$$$ carriages that are numbered from $$$1$$$ to $$$N$$$ from left to right. Carriage $$$i$$$ initially contains $$$A_i$$$ passengers. All carriages are connected by carriage doors, namely for each $$$i$$$ ($$$1\leq i\leq N-1$$$), carriage $$$i$$$ and carriage $$$i+1$$$ are connected by a two-way door.

Each passenger can move between carriages, but train regulation regulates that for each $$$i$$$, a passenger that starts from carriage $$$i$$$ cannot go through more than $$$D_i$$$ doors.

Define $$$Z$$$ as the most number of passengers in one same carriage after moving. Pak Chanek asks, what is the minimum possible value of $$$Z$$$?

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

The second line contains $$$N$$$ integers $$$A_1, A_2, A_3, \ldots, A_N$$$ ($$$0 \leq A_i \leq 10^9$$$) — the initial number of passengers in each carriage.

The third line contains $$$N$$$ integers $$$D_1, D_2, D_3, \ldots, D_N$$$ ($$$0 \leq D_i \leq N-1$$$) — the maximum limit of the number of doors for each starting carriage.

## Output Format
An integer representing the minimum possible value of $$$Z$$$.

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

## Note
One strategy that is optimal is as follows:

- $$$5$$$ people in carriage $$$1$$$ move to carriage $$$4$$$ (going through $$$3$$$ doors).
- $$$3$$$ people in carriage $$$5$$$ move to carriage $$$3$$$ (going through $$$2$$$ doors).
- $$$2$$$ people in carriage $$$6$$$ move to carriage $$$5$$$ (going through $$$1$$$ door).
- $$$1$$$ person in carriage $$$6$$$ moves to carriage $$$7$$$ (going through $$$1$$$ door).

The number of passengers in each carriage becomes $$$[2,4,5,5,4,5,4]$$$.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Define a set $$$A$$$ as a child of set $$$B$$$ if and only if for each element of value $$$x$$$ that is in $$$A$$$, there exists an element of value $$$x+1$$$ that is in $$$B$$$.

Given integers $$$N$$$ and $$$K$$$. In order to make Chaneka happy, you must find the number of different arrays containing $$$N$$$ sets $$$[S_1, S_2, S_3, \ldots, S_N]$$$ such that: - Each set can only contain zero or more different integers from $$$1$$$ to $$$K$$$. - There exists a way to rearrange the order of the array of sets into $$$[S'_1, S'_2, S'_3, \ldots, S'_N]$$$ such that $$$S'_i$$$ is a child of $$$S'_{i+1}$$$ for each $$$1\leq i\leq N-1$$$.

Print the answer modulo $$$998\,244\,353$$$.

Two sets are considered different if and only if there is at least one value that only occurs in one of the two sets.

Two arrays of sets are considered different if and only if there is at least one index $$$i$$$ such that the sets at index $$$i$$$ in the two arrays are different.

## Input Format
The only line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N,K \leq 2\cdot10^5$$$) — the number of sets in the array and the maximum limit for the values in the sets.

## Output Format
An integer representing the number of different arrays of sets that satisfy the problem condition, modulo $$$998\,244\,353$$$.

## Examples
```input
2 2
```
```output
11
```
-----
```input
1 3
```
```output
8
```
-----
```input
3 1
```
```output
4
```

## Note
In the first example, there are $$$11$$$ different arrays of sets possible, which are:

- $$$[\{\}, \{\}]$$$
- $$$[\{\}, \{1\}]$$$
- $$$[\{\}, \{1, 2\}]$$$
- $$$[\{\}, \{2\}]$$$
- $$$[\{1\}, \{\}]$$$
- $$$[\{1\}, \{1, 2\}]$$$
- $$$[\{1\}, \{2\}]$$$
- $$$[\{1, 2\}, \{\}]$$$
- $$$[\{1, 2\}, \{1\}]$$$
- $$$[\{2\}, \{\}]$$$
- $$$[\{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 c++17.

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

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

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
There 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 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
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 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 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 c++17.

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an 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.