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: 4.0 seconds
Memory limit: 1024.0 MB

# Problem
Let's call two numbers similar if their binary representations contain the same number of digits equal to $$$1$$$. For example:

- $$$2$$$ and $$$4$$$ are similar (binary representations are $$$10$$$ and $$$100$$$);
- $$$1337$$$ and $$$4213$$$ are similar (binary representations are $$$10100111001$$$ and $$$1000001110101$$$);
- $$$3$$$ and $$$2$$$ are not similar (binary representations are $$$11$$$ and $$$10$$$);
- $$$42$$$ and $$$13$$$ are similar (binary representations are $$$101010$$$ and $$$1101$$$).

You are given an array of $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$. You may choose a non-negative integer $$$x$$$, and then get another array of $$$n$$$ integers $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$, where $$$b_i = a_i \oplus x$$$ ($$$\oplus$$$ denotes bitwise XOR).

Is it possible to obtain an array $$$b$$$ where all numbers are similar to each other?

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 100$$$).

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i \le 2^{30} - 1$$$).

## Output Format
If it is impossible to choose $$$x$$$ so that all elements in the resulting array are similar to each other, print one integer $$$-1$$$.

Otherwise, print any non-negative integer not exceeding $$$2^{30} - 1$$$ that can be used as $$$x$$$ so that all elements in the resulting array are similar.

## Examples
```input
2
7 2
```
```output
1
```
-----
```input
4
3 17 6 0
```
```output
5
```
-----
```input
3
1 2 3
```
```output
-1
```
-----
```input
3
43 12 12
```
```output
1073709057
```

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

# Problem
You are given an integer $$$x$$$ represented as a product of $$$n$$$ its prime divisors $$$p_1 \cdot p_2, \cdot \ldots \cdot p_n$$$. Let $$$S$$$ be the set of all positive integer divisors of $$$x$$$ (including $$$1$$$ and $$$x$$$ itself).

We call a set of integers $$$D$$$ good if (and only if) there is no pair $$$a \in D$$$, $$$b \in D$$$ such that $$$a \ne b$$$ and $$$a$$$ divides $$$b$$$.

Find a good subset of $$$S$$$ with maximum possible size. Since the answer can be large, print the size of the subset modulo $$$998244353$$$.

## Input Format
The first line contains the single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of prime divisors in representation of $$$x$$$.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$2 \le p_i \le 3 \cdot 10^6$$$) — the prime factorization of $$$x$$$.

## Output Format
Print the maximum possible size of a good subset modulo $$$998244353$$$.

## Examples
```input
3
2999999 43 2999957
```
```output
3
```
-----
```input
6
2 3 2 3 2 2
```
```output
3
```

## Note
In the first sample, $$$x = 2999999 \cdot 43 \cdot 2999957$$$ and one of the maximum good subsets is $$$\{ 43, 2999957, 2999999 \}$$$.

In the second sample, $$$x = 2 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 2 = 144$$$ and one of the maximum good subsets is $$$\{ 9, 12, 16 \}$$$.

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
Bob is a competitive programmer. He wants to become red, and for that he needs a strict training regime. He went to the annual meeting of grandmasters and asked $$$n$$$ of them how much effort they needed to reach red.

"Oh, I just spent $$$x_i$$$ hours solving problems", said the $$$i$$$-th of them.

Bob wants to train his math skills, so for each answer he wrote down the number of minutes ($$$60 \cdot x_i$$$), thanked the grandmasters and went home. Bob could write numbers with leading zeroes — for example, if some grandmaster answered that he had spent $$$2$$$ hours, Bob could write $$$000120$$$ instead of $$$120$$$.

Alice wanted to tease Bob and so she took the numbers Bob wrote down, and for each of them she did one of the following independently:

- rearranged its digits, or
- wrote a random number.

This way, Alice generated $$$n$$$ numbers, denoted $$$y_1$$$, ..., $$$y_n$$$.

For each of the numbers, help Bob determine whether $$$y_i$$$ can be a permutation of a number divisible by $$$60$$$ (possibly with leading zeroes).

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 418$$$) — the number of grandmasters Bob asked.

Then $$$n$$$ lines follow, the $$$i$$$-th of which contains a single integer $$$y_i$$$ — the number that Alice wrote down.

Each of these numbers has between $$$2$$$ and $$$100$$$ digits '0' through '9'. They can contain leading zeroes.

## Output Format
Output $$$n$$$ lines.

For each $$$i$$$, output the following. If it is possible to rearrange the digits of $$$y_i$$$ such that the resulting number is divisible by $$$60$$$, output "red" (quotes for clarity). Otherwise, output "cyan".

## Examples
```input
6
603
006
205
228
1053
0000000000000000000000000000000000000000000000
```
```output
red
red
cyan
cyan
cyan
red
```

## Note
In the first example, there is one rearrangement that yields a number divisible by $$$60$$$, and that is $$$360$$$.

In the second example, there are two solutions. One is $$$060$$$ and the second is $$$600$$$.

In the third example, there are $$$6$$$ possible rearrangments: $$$025$$$, $$$052$$$, $$$205$$$, $$$250$$$, $$$502$$$, $$$520$$$. None of these numbers is divisible by $$$60$$$.

In the fourth example, there are $$$3$$$ rearrangements: $$$228$$$, $$$282$$$, $$$822$$$.

In the fifth example, none of the $$$24$$$ rearrangements result in a number divisible by $$$60$$$.

In the sixth example, note that $$$000\dots0$$$ is a valid solution.

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
Bob is playing with $$$6$$$-sided dice. A net of such standard cube is shown below.

He has an unlimited supply of these dice and wants to build a tower by stacking multiple dice on top of each other, while choosing the orientation of each dice. Then he counts the number of visible pips on the faces of the dice.

For example, the number of visible pips on the tower below is $$$29$$$ — the number visible on the top is $$$1$$$, from the south $$$5$$$ and $$$3$$$, from the west $$$4$$$ and $$$2$$$, from the north $$$2$$$ and $$$4$$$ and from the east $$$3$$$ and $$$5$$$.

The one at the bottom and the two sixes by which the dice are touching are not visible, so they are not counted towards total.

Bob also has $$$t$$$ favourite integers $$$x_i$$$, and for every such integer his goal is to build such a tower that the number of visible pips is exactly $$$x_i$$$. For each of Bob's favourite integers determine whether it is possible to build a tower that has exactly that many visible pips.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of favourite integers of Bob.

The second line contains $$$t$$$ space-separated integers $$$x_i$$$ ($$$1 \leq x_i \leq 10^{18}$$$) — Bob's favourite integers.

## Output Format
For each of Bob's favourite integers, output "YES" if it is possible to build the tower, or "NO" otherwise (quotes for clarity).

## Examples
```input
4
29 34 19 38
```
```output
YES
YES
YES
NO
```

## Note
The first example is mentioned in the problem statement.

In the second example, one can build the tower by flipping the top dice from the previous tower.

In the third example, one can use a single die that has $$$5$$$ on top.

The fourth example is impossible.

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

# Problem
Let $$$G$$$ be a simple graph. Let $$$W$$$ be a non-empty subset of vertices. Then $$$W$$$ is almost-$$$k$$$-uniform if for each pair of distinct vertices $$$u,v \in W$$$ the distance between $$$u$$$ and $$$v$$$ is either $$$k$$$ or $$$k+1$$$.

You are given a tree on $$$n$$$ vertices. For each $$$i$$$ between $$$1$$$ and $$$n$$$, find the maximum size of an almost-$$$i$$$-uniform set.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 5 \cdot 10^5$$$) – the number of vertices of the tree.

Then $$$n-1$$$ lines follows, the $$$i$$$-th of which consisting of two space separated 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$$$.

It is guaranteed that the given graph is tree.

## Output Format
Output a single line containing $$$n$$$ space separated integers $$$a_i$$$, where $$$a_i$$$ is the maximum size of an almost-$$$i$$$-uniform set.

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

## Note
Consider the first example.

- The only maximum almost-$$$1$$$-uniform set is $$$\{1, 2, 3, 4\}$$$.
- One of the maximum almost-$$$2$$$-uniform sets is or $$$\{2, 3, 5\}$$$, another one is $$$\{2, 3, 4\}$$$.
- A maximum almost-$$$3$$$-uniform set is any pair of vertices on distance $$$3$$$.
- Any single vertex is an almost-$$$k$$$-uniform set for $$$k \geq 1$$$.

In the second sample there is an almost-$$$2$$$-uniform set of size $$$4$$$, and that is $$$\{2, 3, 5, 6\}$$$.

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
Let $$$n$$$ be an integer. Consider all permutations on integers $$$1$$$ to $$$n$$$ in lexicographic order, and concatenate them into one big sequence $$$P$$$. For example, if $$$n = 3$$$, then $$$P = [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1]$$$. The length of this sequence is $$$n \cdot n!$$$.

Let $$$1 \leq i \leq j \leq n \cdot n!$$$ be a pair of indices. We call the sequence $$$(P_i, P_{i+1}, \dots, P_{j-1}, P_j)$$$ a subarray of $$$P$$$.

You are given $$$n$$$. Find the number of distinct subarrays of $$$P$$$. Since this number may be large, output it modulo $$$998244353$$$ (a prime number).

## Input Format
The only line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$), as described in the problem statement.

## Output Format
Output a single integer — the number of distinct subarrays, modulo $$$998244353$$$.

## Examples
```input
2
```
```output
8
```
-----
```input
10
```
```output
19210869
```

## Note
In the first example, the sequence $$$P = [1, 2, 2, 1]$$$. It has eight distinct subarrays: $$$[1]$$$, $$$[2]$$$, $$$[1, 2]$$$, $$$[2, 1]$$$, $$$[2, 2]$$$, $$$[1, 2, 2]$$$, $$$[2, 2, 1]$$$ and $$$[1, 2, 2, 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.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp is working on the implementation of displaying likes on the Codehorses social network. The number of likes should be displayed in a format that will be easy to read by users. It was decided that for large numbers of likes the format should be like 123K (one hundred twenty-three thousand) or like 56M (fifty-six million).

The following displaying strategy has been approved:

- the number will be displayed either as an integer number from 0 to 999, or as a positive integer number of thousands (from 1K to 999K), or as a positive integer number of millions (from 1M on),
- the specified exact number of likes $$$n$$$ when displaying should be rounded to the nearest view from the case above (if rounding is ambiguous, it must be rounded up): for example, $$$1785$$$ should be rounded to 2K instead of 1K, $$$4500000$$$ should be rounded to 5M.

Help Polycarp implement this part of the functionality: for a given non-negative integer number of likes $$$n$$$, print its view in the Codehorses interface.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the input. The following are descriptions of the $$$t$$$ input test cases, one per line.

The description of each test case consists of a single line that contains a non-negative integer $$$n$$$ ($$$0 \le n \le 2\cdot10^9$$$) — the number of likes.

## Output Format
Print $$$t$$$ answers to the given test cases in the order from the input. Each printed value must have one of the following types:

- either an integer from 0 to 999 which corresponds just to the number of likes,
- or a number of thousands from 1K to 999K,
- or a number of millions from 1M to 2000M.

The answer is equal to a view which is the closest (by difference) to the given number $$$n$$$. If this rounding is ambiguous, then round answer up (to a greater value).

## Examples
```input
9
999
123
0
1782
31415926
1500
999999
35499710
2000000000
```
```output
999
123
0
2K
31M
2K
1M
35M
2000M
```

## Note
Let's describe some test cases:

- $$$1782$$$ can be displayed either as 1K or as 2K but 2K is the nearest view;
- $$$1500$$$ have same difference with 1K and 2K so it should be rounded up;
- $$$999999$$$ should be displayed as 1M since it's closer to it than to 999K.

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

# Problem
Tanya likes cartoons. She knows that $$$n$$$ new cartoons will be released in his favorite cinema: the $$$i$$$-th of them will be airing from the day $$$a_i$$$ to the day $$$b_i$$$ ($$$1 \le a_i \le b_i \le 10^9$$$).

The cinema has a special offer: there is a huge discount every day when only one cartoon is airing.

Tanya doesn't care which cartoon she will watch but she'd like to save some money. That's why she asks you to find any day $$$x$$$ when only one cartoon will be airing. Formally: find $$$x$$$ such that there is exactly one $$$i$$$ ($$$1 \le i \le n$$$) with $$$a_i \le x \le b_i$$$. If there are several possible answers, print any of them. If there is no such day, print -1.

## Input Format
The first line contains single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The following are descriptions of the $$$t$$$ test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the number of cartoons.

In the next $$$n$$$ lines, the cartoons themselves are described, one per line, by a pair of integers $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i \le b_i \le 10^9$$$) — the first and last airing days for the $$$i$$$-th cartoon.

It is guaranteed that the sum of the values $$$n$$$ for all test cases in the input does not exceed $$$2000$$$.

## Output Format
Print $$$t$$$ answers to given test cases in the order in which they appear in the input: the $$$i$$$-th answer is such $$$x$$$, that only one cartoon will be airing on day $$$x$$$ or -1 if there are no such days.

## Examples
```input
5
1
1 1
3
2 1000000000
2 500000000
500000002 1000000000
3
1 2
3 4
1 4
2
4 11
4 9
3
1 5
10 10
1 5
```
```output
1
500000001
-1
10
10
```

## Note
In the third test case: at day $$$1$$$ and $$$2$$$, first and third cartoons will be airing, and days $$$3$$$ and $$$4$$$, second and third cartoons will be airing. So, there is no day when only one cartoon will be airing.

In the fourth test case, $$$11$$$ is also a possible answer.

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

# Problem
For a given positive integer $$$m$$$, a positive number is called a $$$m$$$-number if the product of its digits is $$$m$$$. For example, the beginning of a series of $$$24$$$-numbers are as follows: $$$38$$$, $$$46$$$, $$$64$$$, $$$83$$$, $$$138$$$, $$$146$$$, $$$164$$$, $$$183$$$, $$$226$$$ ...

You are given a positive integer $$$m$$$ and $$$k$$$. Print $$$k$$$-th among $$$m$$$-numbers if all $$$m$$$-numbers are sorted in ascending order.

## Input Format
A single line of input contains two integers $$$m$$$ and $$$k$$$ ($$$2 \le m \le 10^9$$$, $$$1 \le k \le 10^9$$$).

## Output Format
Print the desired number — $$$k$$$-th among all $$$m$$$-numbers if $$$m$$$-numbers are sorted in ascending order. If the answer does not exist, print -1.

## Examples
```input
24 9
```
```output
226
```
-----
```input
24 1
```
```output
38
```
-----
```input
5040 1000000000
```
```output
111121111315213227111
```
-----
```input
2020 2020
```
```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 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 string $$$s$$$ of lowercase Latin letters. It is required to paint each letter of the string in one of two colors (red or blue) so that if you write all the red letters from left to right and write all the blue letters from left to right, then the lexicographically maximum of the two written strings is lexicographically minimal. For each index, in the string $$$s$$$ you can choose either of two colors.

Formally, we write out:

- the string $$$r$$$ (can be empty) — all red letters in the order from left to right (red subsequence),
- the string $$$b$$$ (can be empty) — all blue letters in the order from left to right (blue subsequence).

Your task is to paint the string such that $$$\max(r, b)$$$ is minimal. Small reminder: the empty string is the lexicographically smallest string.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases in the test. Next, the test cases are given, one per line.

Each test case is a non-empty string $$$s$$$ of length between $$$2$$$ to $$$100$$$ characters, inclusive, which consists of lowercase Latin letters.

## Output Format
Print $$$t$$$ lines, the $$$i$$$-th of them should contain the answer to the $$$i$$$-th test case of the input. Print a string of length $$$n$$$, where $$$n$$$ is the length of the given string $$$s$$$: the $$$j$$$-th character of the string should be either 'R'or 'B' depending on the color of the $$$j$$$-th character in the answer (painted in red or blue). If there are several possible answers, print any of them.

## Examples
```input
5
kotlin
codeforces
abacaba
ffccgc
yz
```
```output
RRRRBB
RRRRRRRBBB
RRRRBBB
RBBBBR
RR
```

Now solve the problem and return the code.