Osijek Competitive Programming Camp, Fall 2023, Day 9: Polish Kids Contest
A. Flips
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a $$$n \times m$$$ board with white or black cells. Each second the board is going to change. For each $$$2 \times 2$$$ square on the previous board, if it doesn't contain two adjacent cells of the same color, all four cells will have their color flipped on the next board. If a cell didn't belong to any of such $$$2 \times 2$$$ squares, its color stays the same. The initial board is in time $$$0$$$. Your task is to answer $$$q$$$ queries. Each query contains one number $$$t$$$ — calculate the number of black cells after $$$t$$$ seconds.

Input

The first line of input contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \leq n, m \leq 2\,000$$$, $$$1 \leq q \leq 200\,000$$$). The next $$$n$$$ lines contain a description of the board. The $$$i$$$-th of these lines contains a string of length $$$m$$$ representing the $$$i$$$-th row. If $$$j$$$-th letter of the string is '#', then cell (i, j) is black. If it's '.' then it's white. The next $$$q$$$ lines contain descriptions of the following queries. In each line there is one integer $$$t$$$ ($$$1 \leq t \leq 10^9$$$) described above.

Output

Output $$$q$$$ lines. In $$$i$$$-th of these lines print the answer to the $$$i$$$-th query from input.

Example
Input
3 4 2
#.#.
##.#
.#.#
1
10
Output
7
6

B. Tree permutations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For a given tree $$$t$$$ of size $$$n$$$, a permutation of length $$$n$$$ is called $$$t$$$-good when there is an edge between nodes $$$i$$$ and $$$j$$$ if and only if there is an edge between nodes $$$p[i]$$$ and $$$p[j]$$$. For a given $$$k$$$, find a tree $$$t$$$ such that there are exactly $$$k$$$ $$$t$$$-good permutations.

Input

The first line of the input contains a single integer $$$k$$$ ($$$2 \leq k \leq 10^{18}$$$).

Output

The first line of the output should contain an integer $$$n$$$ ($$$1 \leq n \leq 400$$$)  — size of a tree or $$$-1$$$ if it does not exist.

If the tree exists, the following $$$n - 1$$$ lines each should contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$)  — the $$$i$$$-th edge of the tree.

Example
Input
2
Output
6
2 1
3 1
4 1
5 4
6 5

C. Control Areas
time limit per test
3.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ vertices. Vertex $$$i$$$ is controlled by mafia $$$m_i$$$. Vertex $$$v$$$ is inside the control area of the $$$i$$$-th mafia iff $$$v$$$ is on the shortest path between any two vertices $$$a$$$ and $$$b$$$ (possibly $$$a = b$$$) controlled by this mafia. Your task is to process $$$q$$$ events of the following two types:

  1. Vertex $$$v$$$ is now controlled by mafia $$$c$$$.
  2. Print the number of control areas that one is going to cross on the shortest path between vertices $$$v$$$ and $$$u$$$. Each vertex has a set control areas it belongs to and we ask for the size of the union of these sets for vertices on a path.
Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 200\,000$$$). The next line contains $$$n$$$ integers $$$m_i$$$ ($$$1 \leq m_i \leq n$$$). The next $$$n - 1$$$ lines describe the edges of the tree. Each of these lines contains two integers $$$v$$$ and $$$u$$$ ($$$1 \leq v, u \leq n$$$) representing an edge between vertices $$$v$$$ and $$$u$$$. The next $$$q$$$ lines describe the events. Each line starts with one integer $$$t$$$ ($$$1 \leq t \leq 2$$$) representing the type of the event. If:

  • $$$t = 1$$$ then two integers $$$v$$$ and $$$c$$$ ($$$1 \leq v, c \leq n$$$) follow;
  • $$$t = 2$$$ then two integers $$$v$$$ and $$$u$$$ ($$$1 \leq v, u \leq n$$$) follow.
Output

Output one line for each event of type $$$2$$$. The $$$i$$$-th of these lines should contain the answer for the $$$i$$$-th such event from the input.

Example
Input
5 4
1 2 3 1 2
1 2
1 3
3 4
1 5
2 2 5
2 1 4
1 1 2
2 2 3
Output
2
3
2

D. Gray Distances
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let's define a sequence of Gray Codes $$$G_n$$$ as follows:

  • if $$$n = 0$$$ then $$$G_n$$$ = {0},
  • if $$$n \gt 0$$$ then $$$G_{n}$$$ is equal to $$$G_{n - 1} \cdot R(G_{n - 1} + 2^{n-1})$$$, where $$$\cdot$$$ means the concatenation of sequences, $$$R(s)$$$ means the reverse of sequence $$$s$$$ and $$$s + c$$$ means sequence $$$s$$$ with every number increased by a constant $$$c$$$.
For example, $$$G_1 = \{0, 1\}$$$, $$$G_2 = \{0, 1, 3, 2\}$$$ and $$$G_3 = \{0, 1, 3, 2, 6, 7, 5, 4\}$$$. For a Gray Code $$$G_n$$$, we define a $$$n \times 2^n$$$ table $$$T_n$$$. The cell in the $$$i$$$-th row and $$$j$$$-th column of $$$T_n$$$ is equal to the $$$i$$$-th least significant bit of the $$$j$$$-th number in the sequence $$$G_n$$$.
01100110
00111100
00001111

The table $$$T_3$$$

Two cells in the table are adjacent if they share a side. The distance between cells $$$(a, b)$$$ and $$$(c, d)$$$, satisfying $$$T_n(a, b) = T_n(c, d) = 1$$$, is defined as the minimal number of moves needed to get from one cell to the other moving only on cells that are $$$1$$$'s. Given $$$n$$$, your task is to calculate the sum of distances between every ordered pair of cells modulo 998 244 353.

Input

The first line of input contains one integer $$$n$$$ ($$$1 \leq n \leq 200\,000$$$).

Output

Print one line containing the answer.

Example
Input
2
Output
20

E. Production Line
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence $$$a$$$ of length $$$n$$$. Your task is to process $$$q$$$ events of the following $$$4$$$ types:

  1. Given $$$x, y$$$ and $$$z$$$, for each $$$1 \leq i \leq n$$$ satisfying $$$x \leq a_i \leq y$$$ change $$$a_i$$$ to $$$z$$$.
  2. Given $$$l, r$$$ and $$$c$$$, for each $$$l \leq i \leq r$$$ change $$$a_i$$$ to $$$c$$$.
  3. Given $$$p$$$, print $$$a_p$$$.
  4. Given $$$p$$$, print the number of $$$1 \leq i \leq n$$$ satisfying $$$a_i \gt a_p$$$.
Input

The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 200\,000$$$). The next line contains $$$n$$$ integers — $$$i$$$-th of them represents $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$). The next $$$q$$$ lines contain descriptions of events. Each line starts with one number $$$t$$$ ($$$1 \leq t \leq 4$$$) representing the type of the event. If:

  1. $$$t = 1$$$ then numbers $$$x, y$$$ and $$$z$$$ follow ($$$1 \leq x \leq y \leq 10^9$$$, $$$1 \leq z \leq 10^9$$$);
  2. $$$t = 2$$$ then numbers $$$l, r$$$ and $$$c$$$ follow ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq c \leq 10^9$$$).
  3. $$$t = 3$$$ or $$$t = 4$$$, then one number $$$p$$$ follows ($$$1 \leq p \leq n$$$).
Output

Output one line for each query of type $$$3$$$ or $$$4$$$. The $$$i$$$-th of them should contain the answer for the $$$i$$$-th such query from the input.

Example
Input
5 8
1 2 3 2 1
4 5
1 1 1 4
4 3
2 1 2 1
4 4
2 2 3 7
4 1
3 4
Output
3
2
2
4
2

F. Is this Fibonacci
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Fibonacci sequence $$$f_i$$$ is defined in the following way: $$$f_0 = f_1 = 1$$$ and for $$$i \gt 1$$$, $$$f_i = f_{i - 1} + f_{i-2}$$$. Given the number $$$k$$$ check if it belongs to the Fibonacci sequence.

Input

The first line of input contains integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$)  — length of the number $$$k$$$. The second line of input contains integer $$$k$$$ of length $$$n$$$.

Output

Print 'YES' (without quotes) if $$$k$$$ belongs to the Fibonacci sequence, and 'NO' (without quotes) otherwise.

Examples
Input
3
610
Output
YES
Input
1
7
Output
NO

G. Queries
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Initially there are two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$ filled with zeros. You need to process $$$q$$$ updates and queries of the following types:

1. For each $$$i$$$ such, that $$$l \leq i \leq r$$$ set $$$a[i] := a[i] + c$$$ and then set $$$b[i] := \max(b[i], a[i])$$$

2. For each $$$i$$$ such, that $$$l \leq i \leq r$$$ set $$$a[i] := \max(a[i], d)$$$ and then set $$$b[i] := \max(b[i], a[i])$$$

3. Print $$$\max(b[l], b[l + 1], ..., b[r])$$$

Input

The first line of the input contains a integers $$$n, q$$$ ($$$1 \leq n,q \leq 5 \cdot 10^5$$$).

The following $$$q$$$ lines of the input start with $$$1 \leq t_i \leq 3$$$ indicating query / update type.

If $$$t_i = 1$$$ the line contains integers $$$l_i, r_i, c_i$$$, ($$$1 \leq l_i \leq r_i \leq n, |c_i| \leq 10^6$$$).

If $$$t_i = 2$$$ the line contains integers $$$l_i, r_i, d_i$$$, ($$$1 \leq l_i \leq r_i \leq n, |d_i| \leq 10^{12}$$$).

If $$$t_i = 3$$$ the line contains integers $$$l_i, r_i$$$, ($$$1 \leq l_i \leq r_i \leq n$$$).

Output

The $$$i$$$-th line of the output should contain the answer to the $$$i$$$-th type 3 query.

Example
Input
10 8
1 1 10 1
1 1 2 2
3 1 7
1 1 5 -100
3 1 3
2 1 6 100
3 7 8
3 6 9
Output
3
3
1
100

H. Gray Rectangles
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let's define a sequence of Gray Codes $$$G_n$$$ as follows:

  • if $$$n = 0$$$ then $$$G_n$$$ = {0},
  • if $$$n \gt 0$$$ then $$$G_{n}$$$ is equal to $$$G_{n - 1} \cdot R(G_{n - 1} + 2^{n-1})$$$, where $$$\cdot$$$ means the concatenation of sequences, $$$R(s)$$$ means the reverse of sequence $$$s$$$ and $$$s + c$$$ means sequence $$$s$$$ with every number increased by a constant $$$c$$$.
For example, $$$G_1 = \{0, 1\}$$$, $$$G_2 = \{0, 1, 3, 2\}$$$ and $$$G_3 = \{0, 1, 3, 2, 6, 7, 5, 4\}$$$. For a Gray Code $$$G_n$$$, we define a $$$n \times 2^n$$$ table $$$T_n$$$. The cell in the $$$i$$$-th row and $$$j$$$-th column of $$$T_n$$$ is equal to the $$$i$$$-th least significant bit of the $$$j$$$-th number in the sequence $$$G_n$$$.
01100110
00111100
00001111

The table $$$T_3$$$

Your task is to answer $$$q$$$ queries. In each query, you are given a number $$$n$$$ and your task is to calculate the number of non-empty rectangles in the table $$$T_n$$$ that contain only $$$1$$$'s modulo 998 244 353.
Input

The first line of input contains one integer $$$q$$$ ($$$1 \leq q \leq 10\,000$$$). The next $$$q$$$ lines each contain one number $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$) described above.

Output

Output $$$q$$$ lines. The $$$i$$$-th line should contain the answer to the $$$i$$$-th query in the input.

Example
Input
3
1
2
3
Output
1
7
32

I. Coprime vertex cover
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a graph $$$G$$$ of $$$n$$$ vertices and $$$m$$$ edges. Find any vertex cover (set of vertices such, that no two non-selected vertices are connected by an edge) $$$C$$$ of this graph such that if $$$a \neq b$$$ and $$$a,b \in C$$$ then $$$\gcd(a, b) = 1$$$.

Input

The first line of the input contains two space-separated integers $$$n, m$$$ ($$$1 \leq n,m \leq 5 \cdot 10^5$$$).

The following $$$m$$$ lines each contain two integers $$$u_i, v_i$$$ ($$$1 \leq u_i \lt v_i \leq n$$$)  — there is an edge between vertex $$$u_i$$$ and vertex $$$v_i$$$.

It is guaranteed that there exists at least one such cover $$$C$$$.

Output

The first line of the output should contain $$$|C|$$$.

The second line of the output should contain $$$|C|$$$ space separated integers  — elements of $$$C$$$.

If there are multiple solutions, print any of them.

Example
Input
5 4
1 2
2 3
3 4
4 5
Output
3
2 3 5

J. Modular Transform
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two arrays $$$a$$$ and $$$b$$$ of length n consisting of values $$$0, 1, 2, 3$$$ and $$$4$$$ you can do the following operation at most $$$8 \cdot n$$$ times:

Choose an index $$$i$$$ and let $$$a[i] := (a[i - 1] + a[i] + a[i + 1]) \mod 5$$$.

All the operations on indices are modulo $$$n$$$.

Check if it is possible to make both arrays equal.

Input

The first line of the input contains single number $$$n$$$ ($$$5 \leq n \leq 10^5$$$)  — the length of both arrays.

The second line contains $$$n$$$ numbers $$$a_0, a_1 ... a_{n - 1}$$$ ($$$0 \leq a_i \leq 4$$$)  — elements of an array.

The third line contains analogous description of array $$$b$$$.

Output

If it is not possible to make both arrays equal output $$$-1$$$.

If it is possible to make both arrays equal the first line should contain $$$0 \leq k \leq 8 \cdot n$$$  — the number of operations.

The following $$$k$$$ lines each should contain a single number $$$0 \leq t_i \leq n - 1$$$  — the index chosen in the $$$i$$$-th operation.

Example
Input
5
1 0 0 1 0
1 0 0 1 1
Output
3
4
4
4