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

# Problem
You're given an integer $$$n$$$. For every integer $$$i$$$ from $$$2$$$ to $$$n$$$, assign a positive integer $$$a_i$$$ such that the following conditions hold:

- For any pair of integers $$$(i,j)$$$, if $$$i$$$ and $$$j$$$ are coprime, $$$a_i \neq a_j$$$.
- The maximal value of all $$$a_i$$$ should be minimized (that is, as small as possible).

A pair of integers is called coprime if their greatest common divisor is $$$1$$$.

## Input Format
The only line contains the integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

## Output Format
Print $$$n-1$$$ integers, $$$a_2$$$, $$$a_3$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \leq a_i \leq n$$$).

If there are multiple solutions, print any of them.

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

## Note
In the first example, notice that $$$3$$$ and $$$4$$$ are coprime, so $$$a_3 \neq a_4$$$. Also, notice that $$$a=[1,2,3]$$$ satisfies the first condition, but it's not a correct answer because its maximal value is $$$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 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
Given two integers $$$n$$$ and $$$x$$$, construct an array that satisfies the following conditions:

- for any element $$$a_i$$$ in the array, $$$1 \le a_i<2^n$$$;
- there is no non-empty subsegment with bitwise XOR equal to $$$0$$$ or $$$x$$$,
- its length $$$l$$$ should be maximized.

A sequence $$$b$$$ is a subsegment of a sequence $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

## Input Format
The only line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 18$$$, $$$1 \le x<2^{18}$$$).

## Output Format
The first line should contain the length of the array $$$l$$$.

If $$$l$$$ is positive, the second line should contain $$$l$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_l$$$ ($$$1 \le a_i < 2^n$$$) — the elements of the array $$$a$$$.

If there are multiple solutions, print any of them.

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

## Note
In the first example, the bitwise XOR of the subsegments are $$$\{6,7,4,1,2,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 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
Let's define a function $$$f(p)$$$ on a permutation $$$p$$$ as follows. Let $$$g_i$$$ be the greatest common divisor (GCD) of elements $$$p_1$$$, $$$p_2$$$, ..., $$$p_i$$$ (in other words, it is the GCD of the prefix of length $$$i$$$). Then $$$f(p)$$$ is the number of distinct elements among $$$g_1$$$, $$$g_2$$$, ..., $$$g_n$$$.

Let $$$f_{max}(n)$$$ be the maximum value of $$$f(p)$$$ among all permutations $$$p$$$ of integers $$$1$$$, $$$2$$$, ..., $$$n$$$.

Given an integers $$$n$$$, count the number of permutations $$$p$$$ of integers $$$1$$$, $$$2$$$, ..., $$$n$$$, such that $$$f(p)$$$ is equal to $$$f_{max}(n)$$$. Since the answer may be large, print the remainder of its division by $$$1000\,000\,007 = 10^9 + 7$$$.

## Input Format
The only line contains the integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the length of the permutations.

## Output Format
The only line should contain your answer modulo $$$10^9+7$$$.

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

## Note
Consider the second example: these are the permutations of length $$$3$$$:

- $$$[1,2,3]$$$, $$$f(p)=1$$$.
- $$$[1,3,2]$$$, $$$f(p)=1$$$.
- $$$[2,1,3]$$$, $$$f(p)=2$$$.
- $$$[2,3,1]$$$, $$$f(p)=2$$$.
- $$$[3,1,2]$$$, $$$f(p)=2$$$.
- $$$[3,2,1]$$$, $$$f(p)=2$$$.

The maximum value $$$f_{max}(3) = 2$$$, and there are $$$4$$$ permutations $$$p$$$ such that $$$f(p)=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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Recall that string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly zero or all) characters. For example, for the string $$$a$$$="wowwo", the following strings are subsequences: "wowwo", "wowo", "oo", "wow", "", and others, but the following are not subsequences: "owoo", "owwwo", "ooo".

The wow factor of a string is the number of its subsequences equal to the word "wow". Bob wants to write a string that has a large wow factor. However, the "w" key on his keyboard is broken, so he types two "v"s instead.

Little did he realise that he may have introduced more "w"s than he thought. Consider for instance the string "ww". Bob would type it as "vvvv", but this string actually contains three occurrences of "w":

- "vvvv"
- "vvvv"
- "vvvv"

For example, the wow factor of the word "vvvovvv" equals to four because there are four wows:

- "vvvovvv"
- "vvvovvv"
- "vvvovvv"
- "vvvovvv"

Note that the subsequence "vvvovvv" does not count towards the wow factor, as the "v"s have to be consecutive.

For a given string $$$s$$$, compute and output its wow factor. Note that it is not guaranteed that it is possible to get $$$s$$$ from another string replacing "w" with "vv". For example, $$$s$$$ can be equal to "vov".

## Input Format
The input contains a single non-empty string $$$s$$$, consisting only of characters "v" and "o". The length of $$$s$$$ is at most $$$10^6$$$.

## Output Format
Output a single integer, the wow factor of $$$s$$$.

## Examples
```input
vvvovvv
```
```output
4
```
-----
```input
vvovooovovvovoovoovvvvovovvvov
```
```output
100
```

## Note
The first example is explained in the legend.

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
Bob is decorating his kitchen, more precisely, the floor. He has found a prime candidate for the tiles he will use. They come in a simple form factor — a square tile that is diagonally split into white and black part as depicted in the figure below.

The dimension of this tile is perfect for this kitchen, as he will need exactly $$$w \times h$$$ tiles without any scraps. That is, the width of the kitchen is $$$w$$$ tiles, and the height is $$$h$$$ tiles. As each tile can be rotated in one of four ways, he still needs to decide on how exactly he will tile the floor. There is a single aesthetic criterion that he wants to fulfil: two adjacent tiles must not share a colour on the edge — i.e. one of the tiles must have a white colour on the shared border, and the second one must be black.

The picture on the left shows one valid tiling of a $$$3 \times 2$$$ kitchen. The picture on the right shows an invalid arrangement, as the bottom two tiles touch with their white parts.

Find the number of possible tilings. As this number may be large, output its remainder when divided by $$$998244353$$$ (a prime number).

## Input Format
The only line contains two space separated integers $$$w$$$, $$$h$$$ ($$$1 \leq w,h \leq 1\,000$$$) — the width and height of the kitchen, measured in tiles.

## Output Format
Output a single integer $$$n$$$ — the remainder of the number of tilings when divided by $$$998244353$$$.

## Examples
```input
2 2
```
```output
16
```
-----
```input
2 4
```
```output
64
```

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
Every person likes prime numbers. Alice is a person, thus she also shares the love for them. Bob wanted to give her an affectionate gift but couldn't think of anything inventive. Hence, he will be giving her a graph. How original, Bob! Alice will surely be thrilled!

When building the graph, he needs four conditions to be satisfied:

- It must be a simple undirected graph, i.e. without multiple (parallel) edges and self-loops.
- The number of vertices must be exactly $$$n$$$ — a number he selected. This number is not necessarily prime.
- The total number of edges must be prime.
- The degree (i.e. the number of edges connected to the vertex) of each vertex must be prime.

Below is an example for $$$n = 4$$$. The first graph (left one) is invalid as the degree of vertex $$$2$$$ (and $$$4$$$) equals to $$$1$$$, which is not prime. The second graph (middle one) is invalid as the total number of edges is $$$4$$$, which is not a prime number. The third graph (right one) is a valid answer for $$$n = 4$$$.

Note that the graph can be disconnected.

Please help Bob to find any such graph!

## Input Format
The input consists of a single integer $$$n$$$ ($$$3 \leq n \leq 1\,000$$$) — the number of vertices.

## Output Format
If there is no graph satisfying the conditions, print a single line containing the integer $$$-1$$$.

Otherwise, first print a line containing a prime number $$$m$$$ ($$$2 \leq m \leq \frac{n(n-1)}{2}$$$) — the number of edges in the graph. Then, print $$$m$$$ lines, the $$$i$$$-th of which containing two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — meaning that there is an edge between vertices $$$u_i$$$ and $$$v_i$$$. The degree of each vertex must be prime. There must be no multiple (parallel) edges or self-loops.

If there are multiple solutions, you may print any of them.

Note that the graph can be disconnected.

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

## Note
The first example was described in the statement.

In the second example, the degrees of vertices are $$$[7, 5, 2, 2, 3, 2, 2, 3]$$$. Each of these numbers is prime. Additionally, the number of edges, $$$13$$$, is also a prime number, hence both conditions are satisfied.

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
Alice bought a Congo Prime Video subscription and was watching a documentary on the archaeological findings from Factor's Island on Loch Katrine in Scotland. The archaeologists found a book whose age and origin are unknown. Perhaps Alice can make some sense of it?

The book contains a single string of characters "a", "b" and "c". It has been pointed out that no two consecutive characters are the same. It has also been conjectured that the string contains an unusually long subsequence that reads the same from both sides.

Help Alice verify this by finding such subsequence that contains at least half of the characters of the original string, rounded down. Note that you don't have to maximise the length of it.

A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters.

## Input Format
The input consists of a single string $$$s$$$ ($$$2 \leq |s| \leq 10^6$$$). The string $$$s$$$ consists only of characters "a", "b", "c". It is guaranteed that no two consecutive characters are equal.

## Output Format
Output a palindrome $$$t$$$ that is a subsequence of $$$s$$$ and $$$|t| \geq \lfloor \frac{|s|}{2} \rfloor$$$.

If there are multiple solutions, you may print any of them. You don't have to maximise the length of $$$t$$$.

If there are no solutions, output a string "IMPOSSIBLE" (quotes for clarity).

## Examples
```input
cacbac
```
```output
aba
```
-----
```input
abc
```
```output
a
```
-----
```input
cbacacacbcbababacbcb
```
```output
cbaaacbcaaabc
```

## Note
In the first example, other valid answers include "cacac", "caac", "aca" and "ccc".

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

# Problem
This is the first subtask of problem F. The only differences between this and the second subtask are the constraints on the value of $$$m$$$ and the time limit. You need to solve both subtasks in order to hack this one.

There are $$$n+1$$$ distinct colours in the universe, numbered $$$0$$$ through $$$n$$$. There is a strip of paper $$$m$$$ centimetres long initially painted with colour $$$0$$$.

Alice took a brush and painted the strip using the following process. For each $$$i$$$ from $$$1$$$ to $$$n$$$, in this order, she picks two integers $$$0 \leq a_i < b_i \leq m$$$, such that the segment $$$[a_i, b_i]$$$ is currently painted with a single colour, and repaints it with colour $$$i$$$.

Alice chose the segments in such a way that each centimetre is now painted in some colour other than $$$0$$$. Formally, the segment $$$[i-1, i]$$$ is painted with colour $$$c_i$$$ ($$$c_i \neq 0$$$). Every colour other than $$$0$$$ is visible on the strip.

Count the number of different pairs of sequences $$$\{a_i\}_{i=1}^n$$$, $$$\{b_i\}_{i=1}^n$$$ that result in this configuration.

Since this number may be large, output it modulo $$$998244353$$$.

## Input Format
The first line contains a two integers $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 500$$$, $$$n = m$$$) — the number of colours excluding the colour $$$0$$$ and the length of the paper, respectively.

The second line contains $$$m$$$ space separated integers $$$c_1, c_2, \ldots, c_m$$$ ($$$1 \leq c_i \leq n$$$) — the colour visible on the segment $$$[i-1, i]$$$ after the process ends. It is guaranteed that for all $$$j$$$ between $$$1$$$ and $$$n$$$ there is an index $$$k$$$ such that $$$c_k = j$$$.

Note that since in this subtask $$$n = m$$$, this means that $$$c$$$ is a permutation of integers $$$1$$$ through $$$n$$$.

## Output Format
Output a single integer — the number of ways Alice can perform the painting, modulo $$$998244353$$$.

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

## Note
In the first example, there are $$$5$$$ ways, all depicted in the figure below. Here, $$$0$$$ is white, $$$1$$$ is red, $$$2$$$ is green and $$$3$$$ is blue.

Below is an example of a painting process that is not valid, as in the second step the segment 1 3 is not single colour, and thus may not be repainted with colour $$$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: 5.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a rooted tree on $$$n$$$ vertices. The vertices are numbered from $$$1$$$ to $$$n$$$; the root is the vertex number $$$1$$$.

Each vertex has two integers associated with it: $$$a_i$$$ and $$$b_i$$$. We denote the set of all ancestors of $$$v$$$ (including $$$v$$$ itself) by $$$R(v)$$$. The awesomeness of a vertex $$$v$$$ is defined as

$$$$$$\left| \sum_{w \in R(v)} a_w\right| \cdot \left|\sum_{w \in R(v)} b_w\right|,$$$$$$

where $$$|x|$$$ denotes the absolute value of $$$x$$$.

Process $$$q$$$ queries of one of the following forms:

- 1 v x — increase $$$a_v$$$ by a positive integer $$$x$$$.
- 2 v — report the maximum awesomeness in the subtree of vertex $$$v$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n \leq 2\cdot 10^5, 1 \leq q \leq 10^5$$$) — the number of vertices in the tree and the number of queries, respectively.

The second line contains $$$n - 1$$$ integers $$$p_2, p_3, \dots, p_n$$$ ($$$1 \leq p_i < i$$$), where $$$p_i$$$ means that there is an edge between vertices $$$i$$$ and $$$p_i$$$.

The third line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-5000 \leq a_i \leq 5000$$$), the initial values of $$$a_i$$$ for each vertex.

The fourth line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$-5000 \leq b_i \leq 5000$$$), the values of $$$b_i$$$ for each vertex.

Each of the next $$$q$$$ lines describes a query. It has one of the following forms:

- 1 v x  ($$$1 \leq v \leq n$$$, $$$1\leq x \leq 5000$$$).
- 2 v  ($$$1 \leq v \leq n$$$).

## Output Format
For each query of the second type, print a single line with the maximum awesomeness in the respective subtree.

## Examples
```input
5 6
1 1 2 2
10 -3 -7 -3 -10
10 3 9 3 6
2 1
2 2
1 2 6
2 1
1 2 5
2 1
```
```output
100
91
169
240
```

## Note
The initial awesomeness of the vertices is $$$[100, 91, 57, 64, 57]$$$. The most awesome vertex in the subtree of vertex $$$1$$$ (the first query) is $$$1$$$, and the most awesome vertex in the subtree of vertex $$$2$$$ (the second query) is $$$2$$$.

After the first update (the third query), the awesomeness changes to $$$[100, 169, 57, 160, 57]$$$ and thus the most awesome vertex in the whole tree (the fourth query) is now $$$2$$$.

After the second update (the fifth query), the awesomeness becomes $$$[100, 234, 57, 240, 152]$$$, hence the most awesome vertex (the sixth query) is now $$$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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Methodius received an email from his friend Polycarp. However, Polycarp's keyboard is broken, so pressing a key on it once may cause the corresponding symbol to appear more than once (if you press a key on a regular keyboard, it prints exactly one symbol).

For example, as a result of typing the word "hello", the following words could be printed: "hello", "hhhhello", "hheeeellllooo", but the following could not be printed: "hell", "helo", "hhllllooo".

Note, that when you press a key, the corresponding symbol must appear (possibly, more than once). The keyboard is broken in a random manner, it means that pressing the same key you can get the different number of letters in the result.

For each word in the letter, Methodius has guessed what word Polycarp actually wanted to write, but he is not sure about it, so he asks you to help him.

You are given a list of pairs of words. For each pair, determine if the second word could be printed by typing the first one on Polycarp's keyboard.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of pairs to check. Further input contains $$$n$$$ descriptions of pairs.

The first line of each description contains a single non-empty word $$$s$$$ consisting of lowercase Latin letters. The second line of the description contains a single non-empty word $$$t$$$ consisting of lowercase Latin letters. The lengths of both strings are not greater than $$$10^6$$$.

It is guaranteed that the total length of all words $$$s$$$ in the input is not greater than $$$10^6$$$. Also, it is guaranteed that the total length of all words $$$t$$$ in the input is not greater than $$$10^6$$$.

## Output Format
Output $$$n$$$ lines. In the $$$i$$$-th line for the $$$i$$$-th pair of words $$$s$$$ and $$$t$$$ print YES if the word $$$t$$$ could be printed by typing the word $$$s$$$. Otherwise, print NO.

## Examples
```input
4
hello
hello
hello
helloo
hello
hlllloo
hello
helo
```
```output
YES
YES
NO
NO
```
-----
```input
5
aa
bb
codeforces
codeforce
polycarp
poolycarpp
aaaa
aaaab
abcdefghijklmnopqrstuvwxyz
zabcdefghijklmnopqrstuvwxyz
```
```output
NO
NO
YES
NO
NO
```

Now solve the problem and return the code.