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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Screen resolution of Polycarp's monitor is $$$a \times b$$$ pixels. Unfortunately, there is one dead pixel at his screen. It has coordinates $$$(x, y)$$$ ($$$0 \le x < a, 0 \le y < b$$$). You can consider columns of pixels to be numbered from $$$0$$$ to $$$a-1$$$, and rows — from $$$0$$$ to $$$b-1$$$.

Polycarp wants to open a rectangular window of maximal size, which doesn't contain the dead pixel. The boundaries of the window should be parallel to the sides of the screen.

Print the maximal area (in pixels) of a window that doesn't contain the dead pixel inside itself.

## Input Format
In the first line you are given an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test. In the next lines you are given descriptions of $$$t$$$ test cases.

Each test case contains a single line which consists of $$$4$$$ integers $$$a, b, x$$$ and $$$y$$$ ($$$1 \le a, b \le 10^4$$$; $$$0 \le x < a$$$; $$$0 \le y < b$$$) — the resolution of the screen and the coordinates of a dead pixel. It is guaranteed that $$$a+b>2$$$ (e.g. $$$a=b=1$$$ is impossible).

## Output Format
Print $$$t$$$ integers — the answers for each test case. Each answer should contain an integer equal to the maximal possible area (in pixels) of a rectangular window, that doesn't contain the dead pixel.

## Examples
```input
6
8 8 0 0
1 10 0 3
17 31 10 4
2 1 0 0
5 10 3 9
10 10 4 8
```
```output
56
6
442
1
45
80
```

## Note
In the first test case, the screen resolution is $$$8 \times 8$$$, and the upper left pixel is a dead pixel. Here you can see one of two possible layouts of the maximal window.

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 sequence $$$b_1, b_2, \ldots, b_n$$$. Find the lexicographically minimal permutation $$$a_1, a_2, \ldots, a_{2n}$$$ such that $$$b_i = \min(a_{2i-1}, a_{2i})$$$, or determine that it is impossible.

## Input Format
Each test contains one or more test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$).

The first line of each test case consists of one integer $$$n$$$ — the number of elements in the sequence $$$b$$$ ($$$1 \le n \le 100$$$).

The second line of each test case consists of $$$n$$$ different integers $$$b_1, \ldots, b_n$$$ — elements of the sequence $$$b$$$ ($$$1 \le b_i \le 2n$$$).

It is guaranteed that the sum of $$$n$$$ by all test cases doesn't exceed $$$100$$$.

## Output Format
For each test case, if there is no appropriate permutation, print one number $$$-1$$$.

Otherwise, print $$$2n$$$ integers $$$a_1, \ldots, a_{2n}$$$ — required lexicographically minimal permutation of numbers from $$$1$$$ to $$$2n$$$.

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

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 tree consisting of $$$n$$$ vertices. A tree is a connected undirected graph with $$$n-1$$$ edges. Each vertex $$$v$$$ of this tree has a color assigned to it ($$$a_v = 1$$$ if the vertex $$$v$$$ is white and $$$0$$$ if the vertex $$$v$$$ is black).

You have to solve the following problem for each vertex $$$v$$$: what is the maximum difference between the number of white and the number of black vertices you can obtain if you choose some subtree of the given tree that contains the vertex $$$v$$$? The subtree of the tree is the connected subgraph of the given tree. More formally, if you choose the subtree that contains $$$cnt_w$$$ white vertices and $$$cnt_b$$$ black vertices, you have to maximize $$$cnt_w - cnt_b$$$.

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

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$), where $$$a_i$$$ is the color of the $$$i$$$-th vertex.

Each of the next $$$n-1$$$ lines describes an edge of the tree. Edge $$$i$$$ is denoted by two integers $$$u_i$$$ and $$$v_i$$$, the labels of vertices it connects $$$(1 \le u_i, v_i \le n, u_i \ne v_i$$$).

It is guaranteed that the given edges form a tree.

## Output Format
Print $$$n$$$ integers $$$res_1, res_2, \dots, res_n$$$, where $$$res_i$$$ is the maximum possible difference between the number of white and black vertices in some subtree that contains the vertex $$$i$$$.

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

## Note
The first example is shown below:

The black vertices have bold borders.

In the second example, the best subtree for vertices $$$2, 3$$$ and $$$4$$$ are vertices $$$2, 3$$$ and $$$4$$$ correspondingly. And the best subtree for the vertex $$$1$$$ is the subtree consisting of vertices $$$1$$$ and $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You have a tree of $$$n$$$ vertices. You are going to convert this tree into $$$n$$$ rubber bands on infinitely large plane. Conversion rule follows:

- For every pair of vertices $$$a$$$ and $$$b$$$, rubber bands $$$a$$$ and $$$b$$$ should intersect if and only if there is an edge exists between $$$a$$$ and $$$b$$$ in the tree.
- Shape of rubber bands must be a simple loop. In other words, rubber band is a loop which doesn't self-intersect.

Now let's define following things:

- Rubber band $$$a$$$ includes rubber band $$$b$$$, if and only if rubber band $$$b$$$ is in rubber band $$$a$$$'s area, and they don't intersect each other.
- Sequence of rubber bands $$$a_{1}, a_{2}, \ldots, a_{k}$$$ ($$$k \ge 2$$$) are nested, if and only if for all $$$i$$$ ($$$2 \le i \le k$$$), $$$a_{i-1}$$$ includes $$$a_{i}$$$.

This is an example of conversion. Note that rubber bands $$$5$$$ and $$$6$$$ are nested.

It can be proved that is it possible to make a conversion and sequence of nested rubber bands under given constraints.

What is the maximum length of sequence of nested rubber bands can be obtained from given tree? Find and print it.

## Input Format
The first line contains integer $$$n$$$ ($$$3 \le n \le 10^{5}$$$) — the number of vertices in tree.

The $$$i$$$-th of the next $$$n-1$$$ lines contains two integers $$$a_{i}$$$ and $$$b_{i}$$$ ($$$1 \le a_{i} \lt b_{i} \le n$$$) — it means there is an edge between $$$a_{i}$$$ and $$$b_{i}$$$. It is guaranteed that given graph forms tree of $$$n$$$ vertices.

## Output Format
Print the answer.

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

## Note
In the first sample, you can obtain a nested sequence of $$$4$$$ rubber bands($$$1$$$, $$$2$$$, $$$5$$$, and $$$6$$$) by the conversion shown below. Of course, there are other conversions exist to make a nested sequence of $$$4$$$ rubber bands. However, you cannot make sequence of $$$5$$$ or more nested rubber bands with given tree.

You can see one of the possible conversions for the second sample below.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two integers $$$x$$$ and $$$y$$$. You can perform two types of operations:

1. Pay $$$a$$$ dollars and increase or decrease any of these integers by $$$1$$$. For example, if $$$x = 0$$$ and $$$y = 7$$$ there are four possible outcomes after this operation:   $$$x = 0$$$, $$$y = 6$$$;  $$$x = 0$$$, $$$y = 8$$$;  $$$x = -1$$$, $$$y = 7$$$;  $$$x = 1$$$, $$$y = 7$$$.
2. Pay $$$b$$$ dollars and increase or decrease both integers by $$$1$$$. For example, if $$$x = 0$$$ and $$$y = 7$$$ there are two possible outcomes after this operation:   $$$x = -1$$$, $$$y = 6$$$;  $$$x = 1$$$, $$$y = 8$$$.

Your goal is to make both given integers equal zero simultaneously, i.e. $$$x = y = 0$$$. There are no other requirements. In particular, it is possible to move from $$$x=1$$$, $$$y=0$$$ to $$$x=y=0$$$.

Calculate the minimum amount of dollars you have to spend on it.

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

The first line of each test case contains two integers $$$x$$$ and $$$y$$$ ($$$0 \le x, y \le 10^9$$$).

The second line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^9$$$).

## Output Format
For each test case print one integer — the minimum amount of dollars you have to spend.

## Examples
```input
2
1 3
391 555
0 0
9 4
```
```output
1337
0
```

## Note
In the first test case you can perform the following sequence of operations: first, second, first. This way you spend $$$391 + 555 + 391 = 1337$$$ dollars.

In the second test case both integers are equal to zero initially, so you dont' have to spend money.

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
Let's say string $$$s$$$ has period $$$k$$$ if $$$s_i = s_{i + k}$$$ for all $$$i$$$ from $$$1$$$ to $$$|s| - k$$$ ($$$|s|$$$ means length of string $$$s$$$) and $$$k$$$ is the minimum positive integer with this property.

Some examples of a period: for $$$s$$$="0101" the period is $$$k=2$$$, for $$$s$$$="0000" the period is $$$k=1$$$, for $$$s$$$="010" the period is $$$k=2$$$, for $$$s$$$="0011" the period is $$$k=4$$$.

You are given string $$$t$$$ consisting only of 0's and 1's and you need to find such string $$$s$$$ that:

1. String $$$s$$$ consists only of 0's and 1's;
2. The length of $$$s$$$ doesn't exceed $$$2 \cdot |t|$$$;
3. String $$$t$$$ is a subsequence of string $$$s$$$;
4. String $$$s$$$ has smallest possible period among all strings that meet conditions 1—3.

Let us recall that $$$t$$$ is a subsequence of $$$s$$$ if $$$t$$$ can be derived from $$$s$$$ by deleting zero or more elements (any) without changing the order of the remaining elements. For example, $$$t$$$="011" is a subsequence of $$$s$$$="10101".

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

Next $$$T$$$ lines contain test cases — one per line. Each line contains string $$$t$$$ ($$$1 \le |t| \le 100$$$) consisting only of 0's and 1's.

## Output Format
Print one string for each test case — string $$$s$$$ you needed to find. If there are multiple solutions print any one of them.

## Examples
```input
4
00
01
111
110
```
```output
00
01
11111
1010
```

## Note
In the first and second test cases, $$$s = t$$$ since it's already one of the optimal solutions. Answers have periods equal to $$$1$$$ and $$$2$$$, respectively.

In the third test case, there are shorter optimal solutions, but it's okay since we don't need to minimize the string $$$s$$$. String $$$s$$$ has period equal to $$$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: 3.5 seconds
Memory limit: 256.0 MB

# Problem
You are given two integers $$$a$$$ and $$$b$$$, and $$$q$$$ queries. The $$$i$$$-th query consists of two numbers $$$l_i$$$ and $$$r_i$$$, and the answer to it is the number of integers $$$x$$$ such that $$$l_i \le x \le r_i$$$, and $$$((x \bmod a) \bmod b) \ne ((x \bmod b) \bmod a)$$$. Calculate the answer for each query.

Recall that $$$y \bmod z$$$ is the remainder of the division of $$$y$$$ by $$$z$$$. For example, $$$5 \bmod 3 = 2$$$, $$$7 \bmod 8 = 7$$$, $$$9 \bmod 4 = 1$$$, $$$9 \bmod 9 = 0$$$.

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

The first line of each test case contains three integers $$$a$$$, $$$b$$$ and $$$q$$$ ($$$1 \le a, b \le 200$$$; $$$1 \le q \le 500$$$).

Then $$$q$$$ lines follow, each containing two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^{18}$$$) for the corresponding query.

## Output Format
For each test case, print $$$q$$$ integers — the answers to the queries of this test case in the order they appear.

## Examples
```input
2
4 6 5
1 1
1 3
1 5
1 7
1 9
7 10 2
7 8
100 200
```
```output
0 0 0 2 4 
0 91
```

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
Calculate the number of ways to place $$$n$$$ rooks on $$$n \times n$$$ chessboard so that both following conditions are met:

- each empty cell is under attack;
- exactly $$$k$$$ pairs of rooks attack each other.

An empty cell is under attack if there is at least one rook in the same row or at least one rook in the same column. Two rooks attack each other if they share the same row or column, and there are no other rooks between them. For example, there are only two pairs of rooks that attack each other in the following picture:

One of the ways to place the rooks for $$$n = 3$$$ and $$$k = 2$$$

Two ways to place the rooks are considered different if there exists at least one cell which is empty in one of the ways but contains a rook in another way.

The answer might be large, so print it modulo $$$998244353$$$.

## Input Format
The only line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 200000$$$; $$$0 \le k \le \frac{n(n - 1)}{2}$$$).

## Output Format
Print one integer — the number of ways to place the rooks, taken modulo $$$998244353$$$.

## Examples
```input
3 2
```
```output
6
```
-----
```input
3 3
```
```output
0
```
-----
```input
4 0
```
```output
24
```
-----
```input
1337 42
```
```output
807905441
```

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
Hmm, how long has it been since the last color revolution? 5 years?! It's totally the time to make a new one!

So the general idea is the following. Division $$$1$$$ should have $$$n_1$$$ participants. Division $$$2$$$ should have $$$n_2$$$ and be exactly $$$k$$$ times bigger than division $$$1$$$ ($$$n_2 = k \cdot n_1$$$). Division $$$3$$$ should have $$$n_3 = k \cdot n_2$$$ participants. Finally, division $$$4$$$ should have $$$n_4 = k \cdot n_3$$$ participants.

There are $$$n$$$ participants on Codeforces in total. So $$$n_1 + n_2 + n_3 + n_4$$$ should be exactly equal to $$$n$$$.

You know the values of $$$n$$$ and $$$k$$$. You also know that $$$n$$$ and $$$k$$$ are chosen in such a way that there exist values $$$n_1, n_2, n_3$$$ and $$$n_4$$$ such that all the conditions are satisfied.

What will be the number of participants in each division ($$$n_1, n_2, n_3$$$ and $$$n_4$$$) after the revolution?

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

Each of the next $$$t$$$ lines contains two integers $$$n$$$ and $$$k$$$ ($$$4 \le n \le 10^9$$$; $$$1 \le k \le 500$$$) — the total number of participants on Codeforces and the size multiplier for the corresponding testcase. In each testcase, $$$n$$$ and $$$k$$$ are chosen in such a way that the answer exists.

## Output Format
For each testcase print four integers $$$n_1, n_2, n_3$$$ and $$$n_4$$$ such that $$$n_2 = k \cdot n_1$$$, $$$n_3 = k \cdot n_2$$$, $$$n_4 = k \cdot n_3$$$ and $$$n_1 + n_2 + n_3 + n_4 = n$$$.

## Examples
```input
4
40 3
1200 7
320802005 400
4 1
```
```output
1 3 9 27
3 21 147 1029
5 2000 800000 320000000
1 1 1 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
Berland State University (BSU) is conducting a programming boot camp. The boot camp will last for $$$n$$$ days, and the BSU lecturers are planning to give some number of lectures during these days.

Some days of the boot camp are already planned as excursion days, and no lectures should be held during these days. To make sure the participants don't get too tired of learning to program, the number of lectures for each day should not exceed $$$k_1$$$, and the number of lectures for each pair of consecutive days should not exceed $$$k_2$$$.

Can you calculate the maximum number of lectures that can be conducted during the boot camp? Formally, find the maximum integer $$$m$$$ such that it is possible to choose $$$n$$$ non-negative integers $$$c_1$$$, $$$c_2$$$, ..., $$$c_n$$$ (where $$$c_i$$$ is the number of lectures held during day $$$i$$$) so that:

- $$$c_1 + c_2 + \dots + c_n = m$$$;
- for each excursion day $$$d$$$, $$$c_d = 0$$$;
- for each day $$$i$$$, $$$c_i \le k_1$$$;
- for each pair of consecutive days $$$(i, i + 1)$$$, $$$c_i + c_{i + 1} \le k_2$$$.

Note that there might be some non-excursion days without lectures (i. e., it is possible that $$$c_i = 0$$$ even if $$$i$$$ is not an excursion day).

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

Then the testcases follow, each consists of two lines. The first line contains three integers $$$n$$$, $$$k_1$$$, $$$k_2$$$ ($$$1 \le n \le 5000$$$; $$$1 \le k_1 \le k_2 \le 200\,000$$$).

The second line contains one string $$$s$$$ consisting of exactly $$$n$$$ characters, each character is either 0 or 1. If $$$s_i = 0$$$, then day $$$i$$$ is an excursion day (so there should be no lectures during that day); if $$$s_i = 1$$$, then day $$$i$$$ is not an excursion day.

## Output Format
For each test case, print one integer — the maximum possible value of $$$m$$$ (the number of lectures that can be conducted).

## Examples
```input
4
4 5 7
1011
4 4 10
0101
5 3 4
11011
6 4 6
011101
```
```output
12
8
8
14
```

Now solve the problem and return the code.