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

# Problem
We just discovered a new data structure in our research group: a suffix three!

It's very useful for natural language processing. Given three languages and three suffixes, a suffix three can determine which language a sentence is written in.

It's super simple, 100% accurate, and doesn't involve advanced machine learning algorithms.

Let us tell you how it works.

- If a sentence ends with "po" the language is Filipino.
- If a sentence ends with "desu" or "masu" the language is Japanese.
- If a sentence ends with "mnida" the language is Korean.

Given this, we need you to implement a suffix three that can differentiate Filipino, Japanese, and Korean.

Oh, did I say three suffixes? I meant four.

## Input Format
The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 30$$$) denoting the number of test cases. The next lines contain descriptions of the test cases.

Each test case consists of a single line containing a single string denoting the sentence. Spaces are represented as underscores (the symbol "_") for ease of reading. The sentence has at least $$$1$$$ and at most $$$1000$$$ characters, and consists only of lowercase English letters and underscores. The sentence has no leading or trailing underscores and no two consecutive underscores. It is guaranteed that the sentence ends with one of the four suffixes mentioned above.

## Output Format
For each test case, print a single line containing either "FILIPINO", "JAPANESE", or "KOREAN" (all in uppercase, without quotes), depending on the detected language.

## Examples
```input
8
kamusta_po
genki_desu
ohayou_gozaimasu
annyeong_hashimnida
hajime_no_ippo
bensamu_no_sentou_houhou_ga_okama_kenpo
ang_halaman_doon_ay_sarisari_singkamasu
si_roy_mustang_ay_namamasu
```
```output
FILIPINO
JAPANESE
JAPANESE
KOREAN
FILIPINO
FILIPINO
JAPANESE
JAPANESE
```

## Note
The first sentence ends with "po", so it is written in Filipino.

The second and third sentences end with "desu" and "masu", so they are written in Japanese.

The fourth sentence ends with "mnida", so it is written in Korean.

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

# Problem
Guy-Manuel and Thomas are planning $$$144$$$ trips around the world.

You are given a simple weighted undirected connected graph with $$$n$$$ vertexes and $$$m$$$ edges with the following restriction: there isn't any simple cycle (i. e. a cycle which doesn't pass through any vertex more than once) of length greater than $$$3$$$ which passes through the vertex $$$1$$$. The cost of a path (not necessarily simple) in this graph is defined as the XOR of weights of all edges in that path with each edge being counted as many times as the path passes through it.

But the trips with cost $$$0$$$ aren't exciting.

You may choose any subset of edges incident to the vertex $$$1$$$ and remove them. How many are there such subsets, that, when removed, there is not any nontrivial cycle with the cost equal to $$$0$$$ which passes through the vertex $$$1$$$ in the resulting graph? A cycle is called nontrivial if it passes through some edge odd number of times. As the answer can be very big, output it modulo $$$10^9+7$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^5$$$) — the number of vertexes and edges in the graph. The $$$i$$$-th of the next $$$m$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$ and $$$w_i$$$ ($$$1 \le a_i, b_i \le n, a_i \neq b_i, 0 \le w_i < 32$$$) — the endpoints of the $$$i$$$-th edge and its weight. It's guaranteed there aren't any multiple edges, the graph is connected and there isn't any simple cycle of length greater than $$$3$$$ which passes through the vertex $$$1$$$.

## Output Format
Output the answer modulo $$$10^9+7$$$.

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

## Note
The pictures below represent the graphs from examples.  In the first example, there aren't any nontrivial cycles with cost $$$0$$$, so we can either remove or keep the only edge incident to the vertex $$$1$$$.  In the second example, if we don't remove the edge $$$1-2$$$, then there is a cycle $$$1-2-4-5-2-1$$$ with cost $$$0$$$; also if we don't remove the edge $$$1-3$$$, then there is a cycle $$$1-3-2-4-5-2-3-1$$$ of cost $$$0$$$. The only valid subset consists of both edges.  In the third example, all subsets are valid except for those two in which both edges $$$1-3$$$ and $$$1-4$$$ are kept.

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 positive integer $$$x$$$. Find any such $$$2$$$ positive integers $$$a$$$ and $$$b$$$ such that $$$GCD(a,b)+LCM(a,b)=x$$$.

As a reminder, $$$GCD(a,b)$$$ is the greatest integer that divides both $$$a$$$ and $$$b$$$. Similarly, $$$LCM(a,b)$$$ is the smallest integer such that both $$$a$$$ and $$$b$$$ divide it.

It's guaranteed that the solution always exists. If there are several such pairs $$$(a, b)$$$, you can output any of them.

## Input Format
The first line contains a single integer $$$t$$$ $$$(1 \le t \le 100)$$$  — the number of testcases.

Each testcase consists of one line containing a single integer, $$$x$$$ $$$(2 \le x \le 10^9)$$$.

## Output Format
For each testcase, output a pair of positive integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^9)$$$ such that $$$GCD(a,b)+LCM(a,b)=x$$$. It's guaranteed that the solution always exists. If there are several such pairs $$$(a, b)$$$, you can output any of them.

## Examples
```input
2
2
14
```
```output
1 1
6 4
```

## Note
In the first testcase of the sample, $$$GCD(1,1)+LCM(1,1)=1+1=2$$$.

In the second testcase of the sample, $$$GCD(6,4)+LCM(6,4)=2+12=14$$$.

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
Ehab has an array $$$a$$$ of length $$$n$$$. He has just enough free time to make a new array consisting of $$$n$$$ copies of the old array, written back-to-back. What will be the length of the new array's longest increasing subsequence?

A sequence $$$a$$$ is a subsequence of an array $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements. The longest increasing subsequence of an array is the longest subsequence such that its elements are ordered in strictly increasing order.

## Input Format
The first line contains an integer $$$t$$$ — the number of test cases you need to solve. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of elements in the array $$$a$$$.

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 $$$a$$$.

The sum of $$$n$$$ across the test cases doesn't exceed $$$10^5$$$.

## Output Format
For each testcase, output the length of the longest increasing subsequence of $$$a$$$ if you concatenate it to itself $$$n$$$ times.

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

## Note
In the first sample, the new array is $$$[3,2,\textbf{1},3,\textbf{2},1,\textbf{3},2,1]$$$. The longest increasing subsequence is marked in bold.

In the second sample, the longest increasing subsequence will be $$$[1,3,4,5,9]$$$.

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
Given 2 integers $$$u$$$ and $$$v$$$, find the shortest array such that bitwise-xor of its elements is $$$u$$$, and the sum of its elements is $$$v$$$.

## Input Format
The only line contains 2 integers $$$u$$$ and $$$v$$$ $$$(0 \le u,v \le 10^{18})$$$.

## Output Format
If there's no array that satisfies the condition, print "-1". Otherwise:

The first line should contain one integer, $$$n$$$, representing the length of the desired array. The next line should contain $$$n$$$ positive integers, the array itself. If there are multiple possible answers, print any.

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

## Note
In the first sample, $$$3\oplus 1 = 2$$$ and $$$3 + 1 = 4$$$. There is no valid array of smaller length.

Notice that in the fourth sample the array is empty.

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
You are given an array $$$a$$$ of length $$$n$$$ that has a special condition: every element in this array has at most 7 divisors. Find the length of the shortest non-empty subsequence of this array product of whose elements is a perfect square.

A sequence $$$a$$$ is a subsequence of an array $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of the array $$$a$$$.

## Output Format
Output the length of the shortest non-empty subsequence of $$$a$$$ product of whose elements is a perfect square. If there are several shortest subsequences, you can find any of them. If there's no such subsequence, print "-1".

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

## Note
In the first sample, you can choose a subsequence $$$[1]$$$.

In the second sample, you can choose a subsequence $$$[6, 6]$$$.

In the third sample, you can choose a subsequence $$$[6, 15, 10]$$$.

In the fourth sample, there is no such subsequence.

Now solve the problem and return the code.