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
Polycarpus likes studying at school a lot and he is always diligent about his homework. Polycarpus has never had any problems with natural sciences as his great-great-grandfather was the great physicist Seinstein. On the other hand though, Polycarpus has never had an easy time with history.

Everybody knows that the World history encompasses exactly n events: the i-th event had continued from the year ai to the year bi inclusive (ai < bi). Polycarpus easily learned the dates when each of n events started and ended (Polycarpus inherited excellent memory from his great-great-granddad). But the teacher gave him a more complicated task: Polycaprus should know when all events began and ended and he should also find out for each event whether it includes another event. Polycarpus' teacher thinks that an event j includes an event i if aj < ai and bi < bj. Your task is simpler: find the number of events that are included in some other event.

## Input Format
The first input line contains integer n (1 ≤ n ≤ 105) which represents the number of events. Next n lines contain descriptions of the historical events, one event per line. The i + 1 line contains two integers ai and bi (1 ≤ ai < bi ≤ 109) — the beginning and the end of the i-th event. No two events start or finish in the same year, that is, ai ≠ aj, ai ≠ bj, bi ≠ aj, bi ≠ bj for all i, j (where i ≠ j). Events are given in arbitrary order.

## Output Format
Print the only integer — the answer to the problem.

## Examples
```input
5
1 10
2 9
3 8
4 7
5 6
```
```output
4
```
-----
```input
5
1 100
2 50
51 99
52 98
10 60
```
```output
4
```
-----
```input
1
1 1000000000
```
```output
0
```

## Note
In the first example the fifth event is contained in the fourth. Similarly, the fourth event is contained in the third, the third — in the second and the second — in the first.

In the second example all events except the first one are contained in the first.

In the third example only one event, so the answer is 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 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 an undirected graph where each edge has one of two colors: black or red.

Your task is to assign a real number to each node so that:

- for each black edge the sum of values at its endpoints is $$$1$$$;
- for each red edge the sum of values at its endpoints is $$$2$$$;
- the sum of the absolute values of all assigned numbers is the smallest possible.

Otherwise, if it is not possible, report that there is no feasible assignment of the numbers.

## Input Format
The first line contains two integers $$$N$$$ ($$$1 \leq N \leq 100\,000$$$) and $$$M$$$ ($$$0 \leq M \leq 200\,000$$$): the number of nodes and the number of edges, respectively. The nodes are numbered by consecutive integers: $$$1, 2, \ldots, N$$$.

The next $$$M$$$ lines describe the edges. Each line contains three integers $$$a$$$, $$$b$$$ and $$$c$$$ denoting that there is an edge between nodes $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq N$$$) with color $$$c$$$ ($$$1$$$ denotes black, $$$2$$$ denotes red).

## Output Format
If there is a solution, the first line should contain the word "YES" and the second line should contain $$$N$$$ space-separated numbers. For each $$$i$$$ ($$$1 \le i \le N$$$), the $$$i$$$-th number should be the number assigned to the node $$$i$$$.

Output should be such that:

- the sum of the numbers at the endpoints of each edge differs from the precise value by less than $$$10^{-6}$$$;
- the sum of the absolute values of all assigned numbers differs from the smallest possible by less than $$$10^{-6}$$$.

If there are several valid solutions, output any of them.

If there is no solution, the only line should contain the word "NO".

## Examples
```input
4 4
1 2 1
2 3 2
1 3 2
3 4 1
```
```output
YES
0.5 0.5 1.5 -0.5
```
-----
```input
2 1
1 2 1
```
```output
YES
0.3 0.7
```
-----
```input
3 2
1 2 2
2 3 2
```
```output
YES
0 2 0
```
-----
```input
3 4
1 2 2
2 2 1
2 1 1
1 2 2
```
```output
NO
```

## Note
Scoring:
Subtasks:

1. (5 points) $$$N \leq 5$$$, $$$M \leq 14$$$
2. (12 points) $$$N \leq 100$$$
3. (17 points) $$$N \leq 1000$$$
4. (24 points) $$$N \leq 10\,000$$$
5. (42 points) No further constraints

Note that in the second example the solution is not unique.

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

# Problem
This problem is split into two tasks. In this task, you are required to find the minimum possible answer. In the task Village (Maximum) you are required to find the maximum possible answer. Each task is worth $$$50$$$ points.

There are $$$N$$$ houses in a certain village. A single villager lives in each of the houses. The houses are connected by roads. Each road connects two houses and is exactly $$$1$$$ kilometer long. From each house it is possible to reach any other using one or several consecutive roads. In total there are $$$N-1$$$ roads in the village.

One day all villagers decided to move to different houses — that is, after moving each house should again have a single villager living in it, but no villager should be living in the same house as before. We would like to know the smallest possible total length in kilometers of the shortest paths between the old and the new houses for all villagers.

Example village with seven houses

For example, if there are seven houses connected by roads as shown on the figure, the smallest total length is $$$8$$$ km (this can be achieved by moving $$$1 \to 6$$$, $$$2 \to 4$$$, $$$3 \to 1$$$, $$$4 \to 2$$$, $$$5 \to 7$$$, $$$6 \to 3$$$, $$$7 \to 5$$$).

Write a program that finds the smallest total length of the shortest paths in kilometers and an example assignment of the new houses to the villagers.

## Input Format
The first line contains an integer $$$N$$$ ($$$1 < N \le 10^5$$$). Houses are numbered by consecutive integers $$$1, 2, \ldots, N$$$.

Then $$$N-1$$$ lines follow that describe the roads. Each line contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le N$$$, $$$a \neq b$$$) denoting that there is a road connecting houses $$$a$$$ and $$$b$$$.

## Output Format
In the first line output the smallest total length of the shortest paths in kilometers.

In the second line describe one valid assignment of the new houses with the smallest total length: $$$N$$$ space-separated distinct integers $$$v_1, v_2, \ldots, v_N$$$. For each $$$i$$$, $$$v_i$$$ is the house number where the villager from the house $$$i$$$ should move ($$$v_i \neq i$$$). If there are several valid assignments, output any of those.

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

## Note
Scoring:
Subtasks:

1. (6 points) $$$N \leq 10$$$
2. (19 points) $$$N \leq 1\,000$$$
3. (25 points) No further constraints

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

# Problem
This problem is split into two tasks. In this task, you are required to find the maximum possible answer. In the task Village (Minimum) you are required to find the minimum possible answer. Each task is worth $$$50$$$ points.

There are $$$N$$$ houses in a certain village. A single villager lives in each of the houses. The houses are connected by roads. Each road connects two houses and is exactly $$$1$$$ kilometer long. From each house it is possible to reach any other using one or several consecutive roads. In total there are $$$N-1$$$ roads in the village.

One day all villagers decided to move to different houses — that is, after moving each house should again have a single villager living in it, but no villager should be living in the same house as before. We would like to know the largest possible total length in kilometers of the shortest paths between the old and the new houses for all villagers.

Example village with seven houses

For example, if there are seven houses connected by roads as shown on the figure, the largest total length is $$$18$$$ km (this can be achieved by moving $$$1 \to 7$$$, $$$2 \to 3$$$, $$$3 \to 4$$$, $$$4 \to 1$$$, $$$5 \to 2$$$, $$$6 \to 5$$$, $$$7 \to 6$$$).

Write a program that finds the largest total length of the shortest paths in kilometers and an example assignment of the new houses to the villagers.

## Input Format
The first line contains an integer $$$N$$$ ($$$1 < N \le 10^5$$$). Houses are numbered by consecutive integers $$$1, 2, \ldots, N$$$.

Then $$$N-1$$$ lines follow that describe the roads. Each line contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le N$$$, $$$a \neq b$$$) denoting that there is a road connecting houses $$$a$$$ and $$$b$$$.

## Output Format
In the first line output the largest total length of the shortest paths in kilometers.

In the second line describe one valid assignment of the new houses with the largest total length: $$$N$$$ space-separated distinct integers $$$v_1, v_2, \ldots, v_N$$$. For each $$$i$$$, $$$v_i$$$ is the house number where villager from the house $$$i$$$ should move ($$$v_i \neq i$$$). If there are several valid assignments, output any of those.

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

## Note
Scoring:
Subtasks:

1. (6 points) $$$N \leq 10$$$
2. (19 points) $$$N \leq 1\,000$$$
3. (25 points) No further constraints

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
One Sunday Petr went to a bookshop and bought a new book on sports programming. The book had exactly n pages.

Petr decided to start reading it starting from the next day, that is, from Monday. Petr's got a very tight schedule and for each day of the week he knows how many pages he will be able to read on that day. Some days are so busy that Petr will have no time to read whatsoever. However, we know that he will be able to read at least one page a week.

Assuming that Petr will not skip days and will read as much as he can every day, determine on which day of the week he will read the last page of the book.

## Input Format
The first input line contains the single integer n (1 ≤ n ≤ 1000) — the number of pages in the book.

The second line contains seven non-negative space-separated integers that do not exceed 1000 — those integers represent how many pages Petr can read on Monday, Tuesday, Wednesday, Thursday, Friday, Saturday and Sunday correspondingly. It is guaranteed that at least one of those numbers is larger than zero.

## Output Format
Print a single number — the number of the day of the week, when Petr will finish reading the book. The days of the week are numbered starting with one in the natural order: Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday.

## Examples
```input
100
15 20 20 15 10 30 45
```
```output
6
```
-----
```input
2
1 0 0 0 0 0 0
```
```output
1
```

## Note
Note to the first sample:

By the end of Monday and therefore, by the beginning of Tuesday Petr has 85 pages left. He has 65 pages left by Wednesday, 45 by Thursday, 30 by Friday, 20 by Saturday and on Saturday Petr finishes reading the book (and he also has time to read 10 pages of something else).

Note to the second sample:

On Monday of the first week Petr will read the first page. On Monday of the second week Petr will read the second page and will finish reading the book.

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
Consider a conveyor belt represented using a grid consisting of $$$n$$$ rows and $$$m$$$ columns. The cell in the $$$i$$$-th row from the top and the $$$j$$$-th column from the left is labelled $$$(i,j)$$$.

Every cell, except $$$(n,m)$$$, has a direction R (Right) or D (Down) assigned to it. If the cell $$$(i,j)$$$ is assigned direction R, any luggage kept on that will move to the cell $$$(i,j+1)$$$. Similarly, if the cell $$$(i,j)$$$ is assigned direction D, any luggage kept on that will move to the cell $$$(i+1,j)$$$. If at any moment, the luggage moves out of the grid, it is considered to be lost.

There is a counter at the cell $$$(n,m)$$$ from where all luggage is picked. A conveyor belt is called functional if and only if any luggage reaches the counter regardless of which cell it is placed in initially. More formally, for every cell $$$(i,j)$$$, any luggage placed in this cell should eventually end up in the cell $$$(n,m)$$$.

This may not hold initially; you are, however, allowed to change the directions of some cells to make the conveyor belt functional. Please determine the minimum amount of cells you have to change.

Please note that it is always possible to make any conveyor belt functional by changing the directions of some set of cells.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$n, m$$$ ($$$1 \le n \le 100$$$, $$$1 \le m \le 100$$$)  — the number of rows and columns, respectively.

The following $$$n$$$ lines each contain $$$m$$$ characters. The $$$j$$$-th character in the $$$i$$$-th line, $$$a_{i,j}$$$ is the initial direction of the cell $$$(i, j)$$$. Please note that $$$a_{n,m}=$$$ C.

## Output Format
For each case, output in a new line the minimum number of cells that you have to change to make the conveyor belt functional.

## Examples
```input
4
3 3
RRD
DDR
RRC
1 4
DDDC
6 9
RDDDDDRRR
RRDDRRDDD
RRDRDRRDR
DDDDRDDRR
DRRDRDDDR
DDRDRRDDC
1 1
C
```
```output
1
3
9
0
```

## Note
In the first case, just changing the direction of $$$(2,3)$$$ to D is enough.

You can verify that the resulting belt is functional. For example, if we place any luggage at $$$(2,2)$$$, it first moves to $$$(3,2)$$$ and then to $$$(3,3)$$$.

In the second case, we have no option but to change the first $$$3$$$ cells from D to R making the grid equal to RRRC.

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
A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Consider a permutation $$$p$$$ of length $$$n$$$, we build a graph of size $$$n$$$ using it as follows:

- For every $$$1 \leq i \leq n$$$, find the largest $$$j$$$ such that $$$1 \leq j < i$$$ and $$$p_j > p_i$$$, and add an undirected edge between node $$$i$$$ and node $$$j$$$
- For every $$$1 \leq i \leq n$$$, find the smallest $$$j$$$ such that $$$i < j \leq n$$$ and $$$p_j > p_i$$$, and add an undirected edge between node $$$i$$$ and node $$$j$$$

In cases where no such $$$j$$$ exists, we make no edges. Also, note that we make edges between the corresponding indices, not the values at those indices.

For clarity, consider as an example $$$n = 4$$$, and $$$p = [3,1,4,2]$$$; here, the edges of the graph are $$$(1,3),(2,1),(2,3),(4,3)$$$.

A permutation $$$p$$$ is cyclic if the graph built using $$$p$$$ has at least one simple cycle.

Given $$$n$$$, find the number of cyclic permutations of length $$$n$$$. Since the number may be very large, output it modulo $$$10^9+7$$$.

Please refer to the Notes section for the formal definition of a simple cycle

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

## Output Format
Output a single integer $$$0 \leq x < 10^9+7$$$, the number of cyclic permutations of length $$$n$$$ modulo $$$10^9+7$$$.

## Examples
```input
4
```
```output
16
```
-----
```input
583291
```
```output
135712853
```

## Note
There are $$$16$$$ cyclic permutations for $$$n = 4$$$. $$$[4,2,1,3]$$$ is one such permutation, having a cycle of length four: $$$4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 4$$$.

Nodes $$$v_1$$$, $$$v_2$$$, $$$\ldots$$$, $$$v_k$$$ form a simple cycle if the following conditions hold:

- $$$k \geq 3$$$.
- $$$v_i \neq v_j$$$ for any pair of indices $$$i$$$ and $$$j$$$. ($$$1 \leq i < j \leq k$$$)
- $$$v_i$$$ and $$$v_{i+1}$$$ share an edge for all $$$i$$$ ($$$1 \leq i < k$$$), and $$$v_1$$$ and $$$v_k$$$ share an edge.

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
A binary matrix is called good if every even length square sub-matrix has an odd number of ones.

Given a binary matrix $$$a$$$ consisting of $$$n$$$ rows and $$$m$$$ columns, determine the minimum number of cells you need to change to make it good, or report that there is no way to make it good at all.

All the terms above have their usual meanings — refer to the Notes section for their formal definitions.

## Input Format
The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq m \leq 10^6$$$ and $$$n\cdot m \leq 10^6$$$)  — the number of rows and columns in $$$a$$$, respectively.

The following $$$n$$$ lines each contain $$$m$$$ characters, each of which is one of 0 and 1. If the $$$j$$$-th character on the $$$i$$$-th line is 1, then $$$a_{i,j} = 1$$$. Similarly, if the $$$j$$$-th character on the $$$i$$$-th line is 0, then $$$a_{i,j} = 0$$$.

## Output Format
Output the minimum number of cells you need to change to make $$$a$$$ good, or output $$$-1$$$ if it's not possible at all.

## Examples
```input
3 3
101
001
110
```
```output
2
```
-----
```input
7 15
000100001010010
100111010110001
101101111100100
010000111111010
111010010100001
000011001111101
111111011010011
```
```output
-1
```

## Note
In the first case, changing $$$a_{1,1}$$$ to $$$0$$$ and $$$a_{2,2}$$$ to $$$1$$$ is enough.

You can verify that there is no way to make the matrix in the second case good.

Some definitions —

- A binary matrix is one in which every element is either $$$1$$$ or $$$0$$$.
- A sub-matrix is described by $$$4$$$ parameters — $$$r_1$$$, $$$r_2$$$, $$$c_1$$$, and $$$c_2$$$; here, $$$1 \leq r_1 \leq r_2 \leq n$$$ and $$$1 \leq c_1 \leq c_2 \leq m$$$.
- This sub-matrix contains all elements $$$a_{i,j}$$$ that satisfy both $$$r_1 \leq i \leq r_2$$$ and $$$c_1 \leq j \leq c_2$$$.
- A sub-matrix is, further, called an even length square if $$$r_2-r_1 = c_2-c_1$$$ and $$$r_2-r_1+1$$$ is divisible by $$$2$$$.

Now solve the problem and return the code.