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

# Problem
Today, Mezo is playing a game. Zoma, a character in that game, is initially at position $$$x = 0$$$. Mezo starts sending $$$n$$$ commands to Zoma. There are two possible commands:

- 'L' (Left) sets the position $$$x: =x - 1$$$;
- 'R' (Right) sets the position $$$x: =x + 1$$$.

Unfortunately, Mezo's controller malfunctions sometimes. Some commands are sent successfully and some are ignored. If the command is ignored then the position $$$x$$$ doesn't change and Mezo simply proceeds to the next command.

For example, if Mezo sends commands "LRLR", then here are some possible outcomes (underlined commands are sent successfully):

- "LRLR" — Zoma moves to the left, to the right, to the left again and to the right for the final time, ending up at position $$$0$$$;
- "LRLR" — Zoma recieves no commands, doesn't move at all and ends up at position $$$0$$$ as well;
- "LRLR" — Zoma moves to the left, then to the left again and ends up in position $$$-2$$$.

Mezo doesn't know which commands will be sent successfully beforehand. Thus, he wants to know how many different positions may Zoma end up at.

## Input Format
The first line contains $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of commands Mezo sends.

The second line contains a string $$$s$$$ of $$$n$$$ commands, each either 'L' (Left) or 'R' (Right).

## Output Format
Print one integer — the number of different positions Zoma may end up at.

## Examples
```input
4
LRLR
```
```output
5
```

## Note
In the example, Zoma may end up anywhere between $$$-2$$$ and $$$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
Today, Osama gave Fadi an integer $$$X$$$, and Fadi was wondering about the minimum possible value of $$$max(a, b)$$$ such that $$$LCM(a, b)$$$ equals $$$X$$$. Both $$$a$$$ and $$$b$$$ should be positive integers.

$$$LCM(a, b)$$$ is the smallest positive integer that is divisible by both $$$a$$$ and $$$b$$$. For example, $$$LCM(6, 8) = 24$$$, $$$LCM(4, 12) = 12$$$, $$$LCM(2, 3) = 6$$$.

Of course, Fadi immediately knew the answer. Can you be just like Fadi and find any such pair?

## Input Format
The first and only line contains an integer $$$X$$$ ($$$1 \le X \le 10^{12}$$$).

## Output Format
Print two positive integers, $$$a$$$ and $$$b$$$, such that the value of $$$max(a, b)$$$ is minimum possible and $$$LCM(a, b)$$$ equals $$$X$$$. If there are several possible such pairs, you can print any.

## Examples
```input
2
```
```output
1 2
```
-----
```input
6
```
```output
2 3
```
-----
```input
4
```
```output
1 4
```
-----
```input
1
```
```output
1 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
Today, as a friendship gift, Bakry gave Badawy $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ and challenged him to choose an integer $$$X$$$ such that the value $$$\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$$$ is minimum possible, where $$$\oplus$$$ denotes the bitwise XOR operation.

As always, Badawy is too lazy, so you decided to help him and find the minimum possible value of $$$\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$$$.

## Input Format
The first line contains integer $$$n$$$ ($$$1\le n \le 10^5$$$).

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

## Output Format
Print one integer — the minimum possible value of $$$\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$$$.

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

## Note
In the first sample, we can choose $$$X = 3$$$.

In the second sample, we can choose $$$X = 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Given an array $$$a$$$, consisting of $$$n$$$ integers, find:

$$$$$$\max\limits_{1 \le i < j \le n} LCM(a_i,a_j),$$$$$$

where $$$LCM(x, y)$$$ is the smallest positive integer that is divisible by both $$$x$$$ and $$$y$$$. For example, $$$LCM(6, 8) = 24$$$, $$$LCM(4, 12) = 12$$$, $$$LCM(2, 3) = 6$$$.

## Input Format
The first line contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of elements in the array $$$a$$$.

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

## Output Format
Print one integer, the maximum value of the least common multiple of two elements in the array $$$a$$$.

## Examples
```input
3
13 35 77
```
```output
1001
```
-----
```input
6
1 2 4 8 16 32
```
```output
32
```

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: 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 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 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 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
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 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 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 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
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.
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
It's the year 5555. You have a graph, and you want to find a long cycle and a huge independent set, just because you can. But for now, let's just stick with finding either.

Given a connected graph with $$$n$$$ vertices, you can choose to either:

- find an independent set that has exactly $$$\lceil\sqrt{n}\rceil$$$ vertices.
- find a simple cycle of length at least $$$\lceil\sqrt{n}\rceil$$$.

An independent set is a set of vertices such that no two of them are connected by an edge. A simple cycle is a cycle that doesn't contain any vertex twice. I have a proof you can always solve one of these problems, but it's too long to fit this margin.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$5 \le n \le 10^5$$$, $$$n-1 \le m \le 2 \cdot 10^5$$$) — the number of vertices and edges in the graph.

Each of the next $$$m$$$ lines contains two space-separated integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$) that mean there's an edge between vertices $$$u$$$ and $$$v$$$. It's guaranteed that the graph is connected and doesn't contain any self-loops or multiple edges.

## Output Format
If you choose to solve the first problem, then on the first line print "1", followed by a line containing $$$\lceil\sqrt{n}\rceil$$$ distinct integers not exceeding $$$n$$$, the vertices in the desired independent set.

If you, however, choose to solve the second problem, then on the first line print "2", followed by a line containing one integer, $$$c$$$, representing the length of the found cycle, followed by a line containing $$$c$$$ distinct integers integers not exceeding $$$n$$$, the vertices in the desired cycle, in the order they appear in the cycle.

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

## Note
In the first sample:

Notice that you can solve either problem, so printing the cycle $$$2-4-3-1-5-6$$$ is also acceptable.

In the second sample:

Notice that if there are multiple answers you can print any, so printing the cycle $$$2-5-6$$$, for example, is acceptable.

In the third sample:

Now solve the problem and return the code.