meetforever/GRPO_CL huggingface dataset:
user: Jzzhu has picked n apples from his big apple tree. All the apples are numbered from 1 to n. Now he wants to sell them to an apple store. 

Jzzhu will pack his apples into groups and then sell them. Each group must contain two apples, and the greatest common divisor of numbers of the apples in each group must be greater than 1. Of course, each apple can be part of at most one group.

Jzzhu wonders how to get the maximum possible number of groups. Can you help him?


-----Input-----

A single integer n (1 ≤ n ≤ 10^5), the number of the apples.


-----Output-----

The first line must contain a single integer m, representing the maximum number of groups he can get. Each of the next m lines must contain two integers — the numbers of apples in the current group.

If there are several optimal answers you can print any of them.


-----Examples-----
Input
6

Output
2
6 3
2 4

Input
9

Output
3
9 3
2 4
6 8

Input
2

Output
0
user: Today Sonya learned about long integers and invited all her friends to share the fun. Sonya has an initially empty multiset with integers. Friends give her t queries, each of one of the following type:   +  a_{i} — add non-negative integer a_{i} to the multiset. Note, that she has a multiset, thus there may be many occurrences of the same integer.   -  a_{i} — delete a single occurrence of non-negative integer a_{i} from the multiset. It's guaranteed, that there is at least one a_{i} in the multiset.  ? s — count the number of integers in the multiset (with repetitions) that match some pattern s consisting of 0 and 1. In the pattern, 0 stands for the even digits, while 1 stands for the odd. Integer x matches the pattern s, if the parity of the i-th from the right digit in decimal notation matches the i-th from the right digit of the pattern. If the pattern is shorter than this integer, it's supplemented with 0-s from the left. Similarly, if the integer is shorter than the pattern its decimal notation is supplemented with the 0-s from the left. 

For example, if the pattern is s = 010, than integers 92, 2212, 50 and 414 match the pattern, while integers 3, 110, 25 and 1030 do not.


-----Input-----

The first line of the input contains an integer t (1 ≤ t ≤ 100 000) — the number of operation Sonya has to perform.

Next t lines provide the descriptions of the queries in order they appear in the input file. The i-th row starts with a character c_{i} — the type of the corresponding operation. If c_{i} is equal to '+' or '-' then it's followed by a space and an integer a_{i} (0 ≤ a_{i} < 10^18) given without leading zeroes (unless it's 0). If c_{i} equals '?' then it's followed by a space and a sequence of zeroes and onse, giving the pattern of length no more than 18.

It's guaranteed that there will be at least one query of type '?'.

It's guaranteed that any time some integer is removed from the multiset, there will be at least one occurrence of this integer in it.


-----Output-----

For each query of the third type print the number of integers matching the given pattern. Each integer is counted as many times, as it appears in the multiset at this moment of time.


-----Examples-----
Input
12
+ 1
+ 241
? 1
+ 361
- 241
? 0101
+ 101
? 101
- 101
? 101
+ 4000
? 0

Output
2
1
2
1
1

Input
4
+ 200
+ 200
- 200
? 0

Output
1



-----Note-----

Consider the integers matching the patterns from the queries of the third type. Queries are numbered in the order they appear in the input.   1 and 241.  361.  101 and 361.  361.  4000.
user: T is playing a game with his friend, HL.

There are $n$ piles of stones, the $i$-th pile initially has $a_i$ stones. 

T and HL will take alternating turns, with T going first. In each turn, a player chooses a non-empty pile and then removes a single stone from it. However, one cannot choose a pile that has been chosen in the previous turn (the pile that was chosen by the other player, or if the current turn is the first turn then the player can choose any non-empty pile). The player who cannot choose a pile in his turn loses, and the game ends.

Assuming both players play optimally, given the starting configuration of $t$ games, determine the winner of each game.


-----Input-----

The first line of the input contains a single integer $t$ $(1 \le t \le 100)$ — the number of games. The description of the games follows. Each description contains two lines:

The first line contains a single integer $n$ $(1 \le n \le 100)$ — the number of piles.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 100)$.


-----Output-----

For each game, print on a single line the name of the winner, "T" or "HL" (without quotes)


-----Example-----
Input
2
1
2
2
1 1

Output
T
HL



-----Note-----

In the first game, T removes a single stone from the only pile in his first turn. After that, although the pile still contains $1$ stone, HL cannot choose from this pile because it has been chosen by T in the previous turn. Therefore, T is the winner.
user: There are n psychos standing in a line. Each psycho is assigned a unique integer from 1 to n. At each step every psycho who has an id greater than the psycho to his right (if exists) kills his right neighbor in the line. Note that a psycho might kill and get killed at the same step. 

You're given the initial arrangement of the psychos in the line. Calculate how many steps are needed to the moment of time such, that nobody kills his neighbor after that moment. Look notes to understand the statement more precise.


-----Input-----

The first line of input contains integer n denoting the number of psychos, (1 ≤ n ≤ 10^5). In the second line there will be a list of n space separated distinct integers each in range 1 to n, inclusive — ids of the psychos in the line from left to right.


-----Output-----

Print the number of steps, so that the line remains the same afterward.


-----Examples-----
Input
10
10 9 7 8 6 5 3 4 2 1

Output
2

Input
6
1 2 3 4 5 6

Output
0



-----Note-----

In the first sample line of the psychos transforms as follows: [10 9 7 8 6 5 3 4 2 1]  →  [10 8 4]  →  [10]. So, there are two steps.
user: You are given a sequence a consisting of n integers. Find the maximum possible value of $a_{i} \operatorname{mod} a_{j}$ (integer remainder of a_{i} divided by a_{j}), where 1 ≤ i, j ≤ n and a_{i} ≥ a_{j}.


-----Input-----

The first line contains integer n — the length of the sequence (1 ≤ n ≤ 2·10^5). 

The second line contains n space-separated integers a_{i} (1 ≤ a_{i} ≤ 10^6).


-----Output-----

Print the answer to the problem.


-----Examples-----
Input
3
3 4 5

Output
2
user: There are n beacons located at distinct positions on a number line. The i-th beacon has position a_{i} and power level b_{i}. When the i-th beacon is activated, it destroys all beacons to its left (direction of decreasing coordinates) within distance b_{i} inclusive. The beacon itself is not destroyed however. Saitama will activate the beacons one at a time from right to left. If a beacon is destroyed, it cannot be activated.

Saitama wants Genos to add a beacon strictly to the right of all the existing beacons, with any position and any power level, such that the least possible number of beacons are destroyed. Note that Genos's placement of the beacon means it will be the first beacon activated. Help Genos by finding the minimum number of beacons that could be destroyed.


-----Input-----

The first line of input contains a single integer n (1 ≤ n ≤ 100 000) — the initial number of beacons.

The i-th of next n lines contains two integers a_{i} and b_{i} (0 ≤ a_{i} ≤ 1 000 000, 1 ≤ b_{i} ≤ 1 000 000) — the position and power level of the i-th beacon respectively. No two beacons will have the same position, so a_{i} ≠ a_{j} if i ≠ j.


-----Output-----

Print a single integer — the minimum number of beacons that could be destroyed if exactly one beacon is added.


-----Examples-----
Input
4
1 9
3 1
6 1
7 4

Output
1

Input
7
1 1
2 1
3 1
4 1
5 1
6 1
7 1

Output
3



-----Note-----

For the first sample case, the minimum number of beacons destroyed is 1. One way to achieve this is to place a beacon at position 9 with power level 2.

For the second sample case, the minimum number of beacons destroyed is 3. One way to achieve this is to place a beacon at position 1337 with power level 42.
user: John Smith knows that his son, Thomas Smith, is among the best students in his class and even in his school. After the students of the school took the exams in English, German, Math, and History, a table of results was formed.

There are $n$ students, each of them has a unique id (from $1$ to $n$). Thomas's id is $1$. Every student has four scores correspond to his or her English, German, Math, and History scores. The students are given in order of increasing of their ids.

In the table, the students will be sorted by decreasing the sum of their scores. So, a student with the largest sum will get the first place. If two or more students have the same sum, these students will be sorted by increasing their ids. 

Please help John find out the rank of his son. 


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 1000$) — the number of students.

Each of the next $n$ lines contains four integers $a_i$, $b_i$, $c_i$, and $d_i$ ($0\leq a_i, b_i, c_i, d_i\leq 100$) — the grades of the $i$-th student on English, German, Math, and History. The id of the $i$-th student is equal to $i$.


-----Output-----

Print the rank of Thomas Smith. Thomas's id is $1$.


-----Examples-----
Input
5
100 98 100 100
100 100 100 100
100 100 99 99
90 99 90 100
100 98 60 99

Output
2

Input
6
100 80 90 99
60 60 60 60
90 60 100 60
60 100 60 80
100 100 0 100
0 0 0 0

Output
1



-----Note-----

In the first sample, the students got total scores: $398$, $400$, $398$, $379$, and $357$. Among the $5$ students, Thomas and the third student have the second highest score, but Thomas has a smaller id, so his rank is $2$.

In the second sample, the students got total scores: $369$, $240$, $310$, $300$, $300$, and $0$. Among the $6$ students, Thomas got the highest score, so his rank is $1$.
user: Barney lives in country USC (United States of Charzeh). USC has n cities numbered from 1 through n and n - 1 roads between them. Cities and roads of USC form a rooted tree (Barney's not sure why it is rooted). Root of the tree is the city number 1. Thus if one will start his journey from city 1, he can visit any city he wants by following roads.

 [Image] 

Some girl has stolen Barney's heart, and Barney wants to find her. He starts looking for in the root of the tree and (since he is Barney Stinson not a random guy), he uses a random DFS to search in the cities. A pseudo code of this algorithm is as follows:



let starting_time be an array of length n

current_time = 0

dfs(v):

        current_time = current_time + 1

        starting_time[v] = current_time

        shuffle children[v] randomly (each permutation with equal possibility)

        // children[v] is vector of children cities of city v

        for u in children[v]:

                dfs(u)



As told before, Barney will start his journey in the root of the tree (equivalent to call dfs(1)).

Now Barney needs to pack a backpack and so he wants to know more about his upcoming journey: for every city i, Barney wants to know the expected value of starting_time[i]. He's a friend of Jon Snow and knows nothing, that's why he asked for your help.


-----Input-----

The first line of input contains a single integer n (1 ≤ n ≤ 10^5) — the number of cities in USC.

The second line contains n - 1 integers p_2, p_3, ..., p_{n} (1 ≤ p_{i} < i), where p_{i} is the number of the parent city of city number i in the tree, meaning there is a road between cities numbered p_{i} and i in USC.


-----Output-----

In the first and only line of output print n numbers, where i-th number is the expected value of starting_time[i].

Your answer for each city will be considered correct if its absolute or relative error does not exceed 10^{ - 6}.


-----Examples-----
Input
7
1 2 1 1 4 4

Output
1.0 4.0 5.0 3.5 4.5 5.0 5.0 

Input
12
1 1 2 2 4 4 3 3 1 10 8

Output
1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0
user: You are given an array of integers. Vasya can permute (change order) its integers. He wants to do it so that as many as possible integers will become on a place where a smaller integer used to stand. Help Vasya find the maximal number of such integers.

For instance, if we are given an array $[10, 20, 30, 40]$, we can permute it so that it becomes $[20, 40, 10, 30]$. Then on the first and the second positions the integers became larger ($20>10$, $40>20$) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals $2$. Read the note for the first example, there is one more demonstrative test case.

Help Vasya to permute integers in such way that the number of positions in a new array, where integers are greater than in the original one, is maximal.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the length of the array.

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


-----Output-----

Print a single integer — the maximal number of the array's elements which after a permutation will stand on the position where a smaller element stood in the initial array.


-----Examples-----
Input
7
10 1 1 1 5 5 3

Output
4

Input
5
1 1 1 1 1

Output
0



-----Note-----

In the first sample, one of the best permutations is $[1, 5, 5, 3, 10, 1, 1]$. On the positions from second to fifth the elements became larger, so the answer for this permutation is 4.

In the second sample, there is no way to increase any element with a permutation, so the answer is 0.
user: You are given a string S of length n with each character being one of the first m lowercase English letters. 

Calculate how many different strings T of length n composed from the first m lowercase English letters exist such that the length of LCS (longest common subsequence) between S and T is n - 1.

Recall that LCS of two strings S and T is the longest string C such that C both in S and T as a subsequence.


-----Input-----

The first line contains two numbers n and m denoting the length of string S and number of first English lowercase characters forming the character set for strings (1 ≤ n ≤ 100 000, 2 ≤ m ≤ 26).

The second line contains string S.


-----Output-----

Print the only line containing the answer.


-----Examples-----
Input
3 3
aaa

Output
6

Input
3 3
aab

Output
11

Input
1 2
a

Output
1

Input
10 9
abacadefgh

Output
789



-----Note-----

For the first sample, the 6 possible strings T are: aab, aac, aba, aca, baa, caa. 

For the second sample, the 11 possible strings T are: aaa, aac, aba, abb, abc, aca, acb, baa, bab, caa, cab.

For the third sample, the only possible string T is b.
user: You are given a string A. Find a string B, where B is a palindrome and A is a subsequence of B.

A subsequence of a string is a string that can be derived from it by deleting some (not necessarily consecutive) characters without changing the order of the remaining characters. For example, "cotst" is a subsequence of "contest".

A palindrome is a string that reads the same forward or backward.

The length of string B should be at most 10^4. It is guaranteed that there always exists such string.

You do not need to find the shortest answer, the only restriction is that the length of string B should not exceed 10^4.


-----Input-----

First line contains a string A (1 ≤ |A| ≤ 10^3) consisting of lowercase Latin letters, where |A| is a length of A.


-----Output-----

Output single line containing B consisting of only lowercase Latin letters. You do not need to find the shortest answer, the only restriction is that the length of string B should not exceed 10^4. If there are many possible B, print any of them.


-----Examples-----
Input
aba

Output
aba
Input
ab

Output
aabaa


-----Note-----

In the first example, "aba" is a subsequence of "aba" which is a palindrome.

In the second example, "ab" is a subsequence of "aabaa" which is a palindrome.
user: There are some ambiguities when one writes Berland names with the letters of the Latin alphabet.

For example, the Berland sound u can be written in the Latin alphabet as "u", and can be written as "oo". For this reason, two words "ulyana" and "oolyana" denote the same name.

The second ambiguity is about the Berland sound h: one can use both "h" and "kh" to write it. For example, the words "mihail" and "mikhail" denote the same name.

There are n users registered on the Polycarp's website. Each of them indicated a name represented by the Latin letters. How many distinct names are there among them, if two ambiguities described above are taken into account?

Formally, we assume that two words denote the same name, if using the replacements "u" [Image] "oo" and "h" [Image] "kh", you can make the words equal. One can make replacements in both directions, in any of the two words an arbitrary number of times. A letter that resulted from the previous replacement can participate in the next replacements.

For example, the following pairs of words denote the same name:  "koouper" and "kuooper". Making the replacements described above, you can make both words to be equal: "koouper" $\rightarrow$ "kuuper" and "kuooper" $\rightarrow$ "kuuper".  "khun" and "kkkhoon". With the replacements described above you can make both words to be equal: "khun" $\rightarrow$ "khoon" and "kkkhoon" $\rightarrow$ "kkhoon" $\rightarrow$ "khoon". 

For a given list of words, find the minimal number of groups where the words in each group denote the same name.


-----Input-----

The first line contains integer number n (2 ≤ n ≤ 400) — number of the words in the list.

The following n lines contain words, one word per line. Each word consists of only lowercase Latin letters. The length of each word is between 1 and 20 letters inclusive.


-----Output-----

Print the minimal number of groups where the words in each group denote the same name.


-----Examples-----
Input
10
mihail
oolyana
kooooper
hoon
ulyana
koouper
mikhail
khun
kuooper
kkkhoon

Output
4

Input
9
hariton
hkariton
buoi
kkkhariton
boooi
bui
khariton
boui
boi

Output
5

Input
2
alex
alex

Output
1



-----Note-----

There are four groups of words in the first example. Words in each group denote same name:  "mihail", "mikhail"  "oolyana", "ulyana"  "kooooper", "koouper"  "hoon", "khun", "kkkhoon" 

There are five groups of words in the second example. Words in each group denote same name:  "hariton", "kkkhariton", "khariton"  "hkariton"  "buoi", "boooi", "boui"  "bui"  "boi" 

In the third example the words are equal, so they denote the same name.
user: Writing light novels is the most important thing in Linova's life. Last night, Linova dreamed about a fantastic kingdom. She began to write a light novel for the kingdom as soon as she woke up, and of course, she is the queen of it.

[Image] 

There are $n$ cities and $n-1$ two-way roads connecting pairs of cities in the kingdom. From any city, you can reach any other city by walking through some roads. The cities are numbered from $1$ to $n$, and the city $1$ is the capital of the kingdom. So, the kingdom has a tree structure.

As the queen, Linova plans to choose exactly $k$ cities developing industry, while the other cities will develop tourism. The capital also can be either industrial or tourism city.

A meeting is held in the capital once a year. To attend the meeting, each industry city sends an envoy. All envoys will follow the shortest path from the departure city to the capital (which is unique).

Traveling in tourism cities is pleasant. For each envoy, his happiness is equal to the number of tourism cities on his path.

In order to be a queen loved by people, Linova wants to choose $k$ cities which can maximize the sum of happinesses of all envoys. Can you calculate the maximum sum for her?


-----Input-----

The first line contains two integers $n$ and $k$ ($2\le n\le 2 \cdot 10^5$, $1\le k< n$)  — the number of cities and industry cities respectively.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1\le u,v\le n$), denoting there is a road connecting city $u$ and city $v$.

It is guaranteed that from any city, you can reach any other city by the roads.


-----Output-----

Print the only line containing a single integer  — the maximum possible sum of happinesses of all envoys.


-----Examples-----
Input
7 4
1 2
1 3
1 4
3 5
3 6
4 7

Output
7
Input
4 1
1 2
1 3
2 4

Output
2
Input
8 5
7 5
1 7
6 1
3 7
8 3
2 1
4 5

Output
9


-----Note-----

[Image]

In the first example, Linova can choose cities $2$, $5$, $6$, $7$ to develop industry, then the happiness of the envoy from city $2$ is $1$, the happiness of envoys from cities $5$, $6$, $7$ is $2$. The sum of happinesses is $7$, and it can be proved to be the maximum one.

[Image]

In the second example, choosing cities $3$, $4$ developing industry can reach a sum of $3$, but remember that Linova plans to choose exactly $k$ cities developing industry, then the maximum sum is $2$.
user: Catherine received an array of integers as a gift for March 8. Eventually she grew bored with it, and she started calculated various useless characteristics for it. She succeeded to do it for each one she came up with. But when she came up with another one — xor of all pairwise sums of elements in the array, she realized that she couldn't compute it for a very large array, thus she asked for your help. Can you do it? Formally, you need to compute

$$ (a_1 + a_2) \oplus (a_1 + a_3) \oplus \ldots \oplus (a_1 + a_n) \\ \oplus (a_2 + a_3) \oplus \ldots \oplus (a_2 + a_n) \\ \ldots \\ \oplus (a_{n-1} + a_n) \\ $$

Here $x \oplus y$ is a bitwise XOR operation (i.e. $x$ ^ $y$ in many modern programming languages). You can read about it in Wikipedia: https://en.wikipedia.org/wiki/Exclusive_or#Bitwise_operation.


-----Input-----

The first line contains a single integer $n$ ($2 \leq n \leq 400\,000$) — the number of integers in the array.

The second line contains integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^7$).


-----Output-----

Print a single integer — xor of all pairwise sums of integers in the given array.


-----Examples-----
Input
2
1 2

Output
3
Input
3
1 2 3

Output
2


-----Note-----

In the first sample case there is only one sum $1 + 2 = 3$.

In the second sample case there are three sums: $1 + 2 = 3$, $1 + 3 = 4$, $2 + 3 = 5$. In binary they are represented as $011_2 \oplus 100_2 \oplus 101_2 = 010_2$, thus the answer is 2.

$\oplus$ is the bitwise xor operation. To define $x \oplus y$, consider binary representations of integers $x$ and $y$. We put the $i$-th bit of the result to be 1 when exactly one of the $i$-th bits of $x$ and $y$ is 1. Otherwise, the $i$-th bit of the result is put to be 0. For example, $0101_2 \, \oplus \, 0011_2 = 0110_2$.