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: 5.0 seconds
Memory limit: 16.0 MB

# Problem
Notice: unusual memory limit!

After the war, destroyed cities in the neutral zone were restored. And children went back to school.

The war changed the world, as well as education. In those hard days, a new math concept was created.

As we all know, logarithm function can be described as: $$$$$$ \log(p_1^{a_1}p_2^{a_2}...p_k^{a_2}) = a_1 \log p_1 + a_2 \log p_2 + ... + a_k \log p_k $$$$$$ Where $$$p_1^{a_1}p_2^{a_2}...p_k^{a_2}$$$ is the prime factorization of a integer. A problem is that the function uses itself in the definition. That is why it is hard to calculate.

So, the mathematicians from the neutral zone invented this: $$$$$$ \text{exlog}_f(p_1^{a_1}p_2^{a_2}...p_k^{a_2}) = a_1 f(p_1) + a_2 f(p_2) + ... + a_k f(p_k) $$$$$$

Notice that $$$\text{exlog}_f(1)$$$ is always equal to $$$0$$$.

This concept for any function $$$f$$$ was too hard for children. So teachers told them that $$$f$$$ can only be a polynomial of degree no more than $$$3$$$ in daily uses (i.e., $$$f(x) = Ax^3+Bx^2+Cx+D$$$).

"Class is over! Don't forget to do your homework!" Here it is: $$$$$$ \sum_{i=1}^n \text{exlog}_f(i) $$$$$$

Help children to do their homework. Since the value can be very big, you need to find the answer modulo $$$2^{32}$$$.

## Input Format
The only line contains five integers $$$n$$$, $$$A$$$, $$$B$$$, $$$C$$$, and $$$D$$$ ($$$1 \le n \le 3 \cdot 10^8$$$, $$$0 \le A,B,C,D \le 10^6$$$).

## Output Format
Print the answer modulo $$$2^{32}$$$.

## Examples
```input
12 0 0 1 0
```
```output
63
```
-----
```input
4 1 2 3 4
```
```output
136
```

## Note
In the first sample:

$$$\text{exlog}_f(1) = 0$$$

$$$\text{exlog}_f(2) = 2$$$

$$$\text{exlog}_f(3) = 3$$$

$$$\text{exlog}_f(4) = 2 + 2 = 4$$$

$$$\text{exlog}_f(5) = 5$$$

$$$\text{exlog}_f(6) = 2 + 3 = 5$$$

$$$\text{exlog}_f(7) = 7$$$

$$$\text{exlog}_f(8) = 2 + 2 + 2 = 6$$$

$$$\text{exlog}_f(9) = 3 + 3 = 6$$$

$$$\text{exlog}_f(10) = 2 + 5 = 7$$$

$$$\text{exlog}_f(11) = 11$$$

$$$\text{exlog}_f(12) = 2 + 2 + 3 = 7$$$

$$$ \sum_{i=1}^{12} \text{exlog}_f(i)=63 $$$

In the second sample:

$$$\text{exlog}_f(1) = 0$$$

$$$\text{exlog}_f(2) = (1 \times 2^3 + 2 \times 2^2 + 3 \times 2 + 4) = 26$$$

$$$\text{exlog}_f(3) = (1 \times 3^3 + 2 \times 3^2 + 3 \times 3 + 4) = 58$$$

$$$\text{exlog}_f(4) = 2 \times \text{exlog}_f(2) = 52$$$

$$$ \sum_{i=1}^4 \text{exlog}_f(i)=0+26+58+52=136 $$$

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
Abendsen assigned a mission to Juliana. In this mission, Juliana has a rooted tree with $$$n$$$ vertices. Vertex number $$$1$$$ is the root of this tree. Each vertex can be either black or white. At first, all vertices are white. Juliana is asked to process $$$q$$$ queries. Each query is one of three types:

1. If vertex $$$v$$$ is white, mark it as black; otherwise, perform this operation on all direct sons of $$$v$$$ instead.
2. Mark all vertices in the subtree of $$$v$$$ (including $$$v$$$) as white.
3. Find the color of the $$$i$$$-th vertex.

An example of operation "1 1" (corresponds to the first example test). The vertices $$$1$$$ and $$$2$$$ are already black, so the operation goes to their sons instead.

Can you help Juliana to process all these queries?

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

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

Each of the next $$$q$$$ lines contains two integers $$$t_i$$$ and $$$v_i$$$ ($$$1\leq t_i\leq 3$$$, $$$1\leq v_i\leq n$$$) — the type of the $$$i$$$-th query and the vertex of the $$$i$$$-th query.

It is guaranteed that the given graph is a tree.

## Output Format
For each query of type $$$3$$$, print "black" if the vertex is black; otherwise, print "white".

## Examples
```input
8 10
1 2 1 2 5 4 5
1 2
3 2
3 1
1 1
1 1
3 5
3 7
3 4
2 2
3 5
```
```output
black
white
black
white
black
white
```
-----
```input
8 11
1 1 2 3 3 6 6
1 1
1 1
1 3
3 2
3 4
3 6
3 7
2 3
1 6
3 7
3 6
```
```output
black
white
black
white
white
black
```

## Note
The first example is shown on the picture below.

The second example is shown on the picture 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 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 an integer $$$x$$$, find 2 integers $$$a$$$ and $$$b$$$ such that:

- $$$1 \le a,b \le x$$$
- $$$b$$$ divides $$$a$$$ ($$$a$$$ is divisible by $$$b$$$).
- $$$a \cdot b>x$$$.
- $$$\frac{a}{b}<x$$$.

## Input Format
The only line contains the integer $$$x$$$ $$$(1 \le x \le 100)$$$.

## Output Format
You should output two integers $$$a$$$ and $$$b$$$, satisfying the given conditions, separated by a space. If no pair of integers satisfy the conditions above, print "-1" (without quotes).

## Examples
```input
10
```
```output
6 3
```
-----
```input
1
```
```output
-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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You're given an array $$$a$$$. You should repeat the following operation $$$k$$$ times: find the minimum non-zero element in the array, print it, and then subtract it from all the non-zero elements of the array. If all the elements are 0s, just print 0.

## Input Format
The first line contains integers $$$n$$$ and $$$k$$$ $$$(1 \le n,k \le 10^5)$$$, the length of the array and the number of operations you should perform.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$, the elements of the array.

## Output Format
Print the minimum non-zero element before each operation in a new line.

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

## Note
In the first sample:

In the first step: the array is $$$[1,2,3]$$$, so the minimum non-zero element is 1.

In the second step: the array is $$$[0,1,2]$$$, so the minimum non-zero element is 1.

In the third step: the array is $$$[0,0,1]$$$, so the minimum non-zero element is 1.

In the fourth and fifth step: the array is $$$[0,0,0]$$$, so we printed 0.

In the second sample:

In the first step: the array is $$$[10,3,5,3]$$$, so the minimum non-zero element is 3.

In the second step: the array is $$$[7,0,2,0]$$$, so the minimum non-zero element is 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
You're given an array $$$a$$$ of length $$$n$$$. You can perform the following operations on it:

- choose an index $$$i$$$ $$$(1 \le i \le n)$$$, an integer $$$x$$$ $$$(0 \le x \le 10^6)$$$, and replace $$$a_j$$$ with $$$a_j+x$$$ for all $$$(1 \le j \le i)$$$, which means add $$$x$$$ to all the elements in the prefix ending at $$$i$$$.
- choose an index $$$i$$$ $$$(1 \le i \le n)$$$, an integer $$$x$$$ $$$(1 \le x \le 10^6)$$$, and replace $$$a_j$$$ with $$$a_j \% x$$$ for all $$$(1 \le j \le i)$$$, which means replace every element in the prefix ending at $$$i$$$ with the remainder after dividing it by $$$x$$$.

Can you make the array strictly increasing in no more than $$$n+1$$$ operations?

## Input Format
The first line contains an integer $$$n$$$ $$$(1 \le n \le 2000)$$$, the number of elements in the array $$$a$$$.

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_n$$$ $$$(0 \le a_i \le 10^5)$$$, the elements of the array $$$a$$$.

## Output Format
On the first line, print the number of operations you wish to perform. On the next lines, you should print the operations.

To print an adding operation, use the format "$$$1$$$ $$$i$$$ $$$x$$$"; to print a modding operation, use the format "$$$2$$$ $$$i$$$ $$$x$$$". If $$$i$$$ or $$$x$$$ don't satisfy the limitations above, or you use more than $$$n+1$$$ operations, you'll get wrong answer verdict.

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

## Note
In the first sample, the array is already increasing so we don't need any operations.

In the second sample:

In the first step: the array becomes $$$[8,6,3]$$$.

In the second step: the array becomes $$$[0,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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You're given a tree consisting of $$$n$$$ nodes. Every node $$$u$$$ has a weight $$$a_u$$$. You want to choose an integer $$$k$$$ $$$(1 \le k \le n)$$$ and then choose $$$k$$$ connected components of nodes that don't overlap (i.e every node is in at most 1 component). Let the set of nodes you chose be $$$s$$$. You want to maximize:

$$$$$$\frac{\sum\limits_{u \in s} a_u}{k}$$$$$$

In other words, you want to maximize the sum of weights of nodes in $$$s$$$ divided by the number of connected components you chose. Also, if there are several solutions, you want to maximize $$$k$$$.

Note that adjacent nodes can belong to different components. Refer to the third sample.

## Input Format
The first line contains the integer $$$n$$$ $$$(1 \le n \le 3 \cdot 10^5)$$$, the number of nodes in the tree.

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_n$$$ $$$(|a_i| \le 10^9)$$$, the weights of the nodes.

The next $$$n-1$$$ lines, each contains 2 space-separated integers $$$u$$$ and $$$v$$$ $$$(1 \le u,v \le n)$$$ which means there's an edge between $$$u$$$ and $$$v$$$.

## Output Format
Print the answer as a non-reduced fraction represented by 2 space-separated integers. The fraction itself should be maximized and if there are several possible ways, you should maximize the denominator. See the samples for a better understanding.

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

## Note
A connected component is a set of nodes such that for any node in the set, you can reach all other nodes in the set passing only nodes in the set.

In the first sample, it's optimal to choose the whole tree.

In the second sample, you only have one choice (to choose node 1) because you can't choose 0 components.

In the third sample, notice that we could've, for example, chosen only node 1, or node 1 and node 3, or even the whole tree, and the fraction would've had the same value (-1), but we want to maximize $$$k$$$.

In the fourth sample, we'll just choose nodes 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 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
Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya got an array consisting of n numbers, it is the gift for his birthday. Now he wants to sort it in the non-decreasing order. However, a usual sorting is boring to perform, that's why Petya invented the following limitation: one can swap any two numbers but only if at least one of them is lucky. Your task is to sort the array according to the specified limitation. Find any possible sequence of the swaps (the number of operations in the sequence should not exceed 2n).

## Input Format
The first line contains an integer n (1 ≤ n ≤ 105) — the number of elements in the array. The second line contains n positive integers, not exceeding 109 — the array that needs to be sorted in the non-decreasing order.

## Output Format
On the first line print number k (0 ≤ k ≤ 2n) — the number of the swaps in the sorting. On the following k lines print one pair of distinct numbers (a pair per line) — the indexes of elements to swap. The numbers in the array are numbered starting from 1. If it is impossible to sort the given sequence, print the single number -1.

If there are several solutions, output any. Note that you don't have to minimize k. Any sorting with no more than 2n swaps is accepted.

## Examples
```input
2
4 7
```
```output
0
```
-----
```input
3
4 2 1
```
```output
1
1 3
```
-----
```input
7
77 66 55 44 33 22 11
```
```output
7
1 7
7 2
2 6
6 7
3 4
5 3
4 5
```

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

# Problem
Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

One day Petya came across an interval of numbers [a, a + l - 1]. Let F(x) be the number of lucky digits of number x. Find the minimum b (a < b) such, that F(a) = F(b), F(a + 1) = F(b + 1), ..., F(a + l - 1) = F(b + l - 1).

## Input Format
The single line contains two integers a and l (1 ≤ a, l ≤ 109) — the interval's first number and the interval's length correspondingly.

## Output Format
On the single line print number b — the answer to the problem.

## Examples
```input
7 4
```
```output
17
```
-----
```input
4 7
```
```output
14
```

## Note
Consider that [a, b] denotes an interval of integers; this interval includes the boundaries. That is, $$\left[a,b\right] \stackrel{\mathrm{def}}{=}\{x\in\mathbb{R}:a\leqslant x\leqslant b\}$$

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

# Problem
One fine day Sasha went to the park for a walk. In the park, he saw that his favorite bench is occupied, and he had to sit down on the neighboring one. He sat down and began to listen to the silence. Suddenly, he got a question: what if in different parts of the park, the silence sounds in different ways? So it was. Let's divide the park into $$$1 \times 1$$$ meter squares and call them cells, and numerate rows from $$$1$$$ to $$$n$$$ from up to down, and columns from $$$1$$$ to $$$m$$$ from left to right. And now, every cell can be described with a pair of two integers $$$(x, y)$$$, where $$$x$$$ — the number of the row, and $$$y$$$ — the number of the column. Sasha knows that the level of silence in the cell $$$(i, j)$$$ equals to $$$f_{i,j}$$$, and all $$$f_{i,j}$$$ form a permutation of numbers from $$$1$$$ to $$$n \cdot m$$$. Sasha decided to count, how many are there pleasant segments of silence?

Let's take some segment $$$[l \ldots r]$$$. Denote $$$S$$$ as the set of cells $$$(i, j)$$$ that $$$l \le f_{i,j} \le r$$$. Then, the segment of silence $$$[l \ldots r]$$$ is pleasant if there is only one simple path between every pair of cells from $$$S$$$ (path can't contain cells, which are not in $$$S$$$). In other words, set $$$S$$$ should look like a tree on a plain. Sasha has done this task pretty quickly, and called the algorithm — "algorithm of silence's sounds".

Time passed, and the only thing left from the algorithm is a legend. To prove the truthfulness of this story, you have to help Sasha and to find the number of different pleasant segments of silence. Two segments $$$[l_1 \ldots r_1]$$$, $$$[l_2 \ldots r_2]$$$ are different, if $$$l_1 \neq l_2$$$ or $$$r_1 \neq r_2$$$ or both at the same time.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 1000$$$, $$$1 \le n \cdot m \le 2 \cdot 10^5$$$) — the size of the park.

Each from next $$$n$$$ lines contains $$$m$$$ integers $$$f_{i,j}$$$ ($$$1 \le f_{i,j} \le n \cdot m$$$) — the level of silence in the cell with number $$$(i, j)$$$.

It is guaranteed, that all $$$f_{i,j}$$$ are different.

## Output Format
Print one integer — the number of pleasant segments of silence.

## Examples
```input
1 5
1 2 3 4 5
```
```output
15
```
-----
```input
2 3
1 2 3
4 5 6
```
```output
15
```
-----
```input
4 4
4 3 2 16
1 13 14 15
5 7 8 12
6 11 9 10
```
```output
50
```

## Note
In the first example, all segments of silence are pleasant.

In the second example, pleasant segments of silence are the following:

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
We all know that a superhero can transform to certain other superheroes. But not all Superheroes can transform to any other superhero. A superhero with name $$$s$$$ can transform to another superhero with name $$$t$$$ if $$$s$$$ can be made equal to $$$t$$$ by changing any vowel in $$$s$$$ to any other vowel and any consonant in $$$s$$$ to any other consonant. Multiple changes can be made.

In this problem, we consider the letters 'a', 'e', 'i', 'o' and 'u' to be vowels and all the other letters to be consonants.

Given the names of two superheroes, determine if the superhero with name $$$s$$$ can be transformed to the Superhero with name $$$t$$$.

## Input Format
The first line contains the string $$$s$$$ having length between $$$1$$$ and $$$1000$$$, inclusive.

The second line contains the string $$$t$$$ having length between $$$1$$$ and $$$1000$$$, inclusive.

Both strings $$$s$$$ and $$$t$$$ are guaranteed to be different and consist of lowercase English letters only.

## Output Format
Output "Yes" (without quotes) if the superhero with name $$$s$$$ can be transformed to the superhero with name $$$t$$$ and "No" (without quotes) otherwise.

You can print each letter in any case (upper or lower).

## Examples
```input
a
u
```
```output
Yes
```
-----
```input
abc
ukm
```
```output
Yes
```
-----
```input
akm
ua
```
```output
No
```

## Note
In the first sample, since both 'a' and 'u' are vowels, it is possible to convert string $$$s$$$ to $$$t$$$.

In the third sample, 'k' is a consonant, whereas 'a' is a vowel, so it is not possible to convert string $$$s$$$ to $$$t$$$.

Now solve the problem and return the code.