vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
For a sequence of strings [t_1, t_2, ..., t_m], let's define the function f([t_1, t_2, ..., t_m]) as the number of different strings (including the empty string) that are subsequences of at least one string t_i. f([]) = 0 (i. e. the number of such strings for an empty sequence is 0).

You are given a sequence of strings [s_1, s_2, ..., s_n]. Every string in this sequence consists of lowercase Latin letters and is sorted (i. e., each string begins with several (maybe zero) characters a, then several (maybe zero) characters b, ..., ends with several (maybe zero) characters z).

For each of 2^n subsequences of [s_1, s_2, ..., s_n], calculate the value of the function f modulo 998244353.

Input

The first line contains one integer n (1 ≤ n ≤ 23) — the number of strings.

Then n lines follow. The i-th line contains the string s_i (1 ≤ |s_i| ≤ 2 ⋅ 10^4), consisting of lowercase Latin letters. Each string s_i is sorted.

Output

Since printing up to 2^{23} integers would be really slow, you should do the following:

For each of the 2^n subsequences (which we denote as [s_{i_1}, s_{i_2}, ..., s_{i_k}]), calculate f([s_{i_1}, s_{i_2}, ..., s_{i_k}]), take it modulo 998244353, then multiply it by k ⋅ (i_1 + i_2 + ... + i_k). Print the XOR of all 2^n integers you get.

The indices i_1, i_2, ..., i_k in the description of each subsequences are 1-indexed (i. e. are from 1 to n).

Examples

Input


3
a
b
c


Output


92


Input


2
aa
a


Output


21


Input


2
a
a


Output


10


Input


2
abcd
aabb


Output


124


Input


3
ddd
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaabbbbbbbbbbbcccccccccccciiiiiiiiiiiiiiiiiiiiiiooooooooooqqqqqqqqqqqqqqqqqqvvvvvzzzzzzzzzzzz


Output


15706243380

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Lightsabers (medium)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There is unrest in the Galactic Senate. Several thousand solar systems have declared their intentions to leave the Republic. Master Heidi needs to select the Jedi Knights who will go on peacekeeping missions throughout the galaxy. It is well-known that the success of any peacekeeping mission depends on the colors of the lightsabers of the Jedi who will go on that mission. 

Heidi has *n* Jedi Knights standing in front of her, each one with a lightsaber of one of *m* possible colors. She knows that for the mission to be the most effective, she needs to select some contiguous interval of knights such that there are exactly *k*1 knights with lightsabers of the first color, *k*2 knights with lightsabers of the second color, ..., *k**m* knights with lightsabers of the *m*-th color.

However, since the last time, she has learned that it is not always possible to select such an interval. Therefore, she decided to ask some Jedi Knights to go on an indefinite unpaid vacation leave near certain pits on Tatooine, if you know what I mean. Help Heidi decide what is the minimum number of Jedi Knights that need to be let go before she is able to select the desired interval from the subsequence of remaining knights.

Input Specification:
The first line of the input contains *n* (1<=≤<=*n*<=≤<=2·105) and *m* (1<=≤<=*m*<=≤<=*n*). The second line contains *n* integers in the range {1,<=2,<=...,<=*m*} representing colors of the lightsabers of the subsequent Jedi Knights. The third line contains *m* integers *k*1,<=*k*2,<=...,<=*k**m* (with ) – the desired counts of Jedi Knights with lightsabers of each color from 1 to *m*.

Output Specification:
Output one number: the minimum number of Jedi Knights that need to be removed from the sequence so that, in what remains, there is an interval with the prescribed counts of lightsaber colors. If this is not possible, output <=-<=1.

Demo Input:
['8 3\n3 3 1 2 2 1 1 3\n3 1 1\n']

Demo Output:
['1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Problem description.
Dominic Toretto has taken his crew to compete in this years' Race Wars, a crew-on-crew tournament in which each member of one crew competes with a member of the other crew in a quarter mile drag race. Each win counts as one point for the winning crew. Draws and loses are awarded zero points. In the end the crew with more points is declared the winner of that round and can advance while the losing crew is knocked out. One member can compete in only one race per round and all crews have the same number of members.
Dom and his crew have a reputation of being the best and naturally everyone expects them to win this year as well.
However, during the tournament he spots a new crew of racers who are participating for the first time in this event. People expect them to be a dark horse so naturally Dom wants to keep an eye on their performance.
Being the experienced racer that he is, Dom has figured out the time in which each racer of the opposing crew completes his quarter mile race.

He also knows his own crew inside out and can estimate with absolute certainty, the time it would take each of his members to complete the race. Dominic is the reigning champion and thus has an advantage that he can select the order of the matches i.e.: he can select which member of his crew will go up against which member of the opposition. Given this data he wants to figure out the number of races he will win should his crew come face to face with their newest rivals.

Unfortunately he is a racer and not a problem solver so he comes to you for help.

Given the time each member of the two crews take to complete the race you have to figure out a way to arrange the matches so that Dominic can win maximum points possible for him.

-----Input-----

The first line of input is the T, the number of test cases.

Each test case starts with a single number N, the number of racers on each crew.

This is followed by two lines, each having N space separated integers containing the time taken by each member of Dominic's crew and the rival crew respectively.

-----Output-----
Output a single integer. The maximum number of points that Dominic can get.

-----Constraints-----
1<=T<=100
1<=N<=100
Time taken by each member will be between 1 and 500

-----Example-----
Input:

1
3
5 4 1
5 4 1

Output:
2

-----Explanation-----
If Dom selects Racer 1 of his team to go against Racer 2 of the other team, Racer 2 of his team against Racer 3 of the other team and Racer 3 of his team against Racer 1 of the other team then he ends up with two wins and a loss which gives him 2 points. ...

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number n, find count of all binary sequences of length 2n such that sum of first n bits is same as sum of last n bits.
The anwer can be very large. So, you have to return answer modulo 10^{9}+7.
Example:
Input: n = 2
Output: 6
Explanation: There are 6 sequences of length 
2*n, the sequences are 0101, 0110, 1010, 1001, 
0000 and 1111.
Example:
Input: n = 1
Output: 2
Explanation: There are 2 sequence of length 
2*n, the sequence are 00 and 11.
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function compute_value() which takes n as input parameter and returns count of all binary sequence of length 2*n such that sum of first n bits is same as sum of last n bits modulo 10^{9} + 7.
 
Expected Time Complexity: O(n * log(n))
Expected Space Complexity:  O(1)
 
Constraints:
1 <= n <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an interactive problem.

Homer likes arrays a lot and he wants to play a game with you. 

Homer has hidden from you a permutation a_1, a_2, ..., a_n of integers 1 to n. You are asked to find any index k (1 ≤ k ≤ n) which is a local minimum. 

For an array a_1, a_2, ..., a_n, an index i (1 ≤ i ≤ n) is said to be a local minimum if a_i < min\\{a_{i-1},a_{i+1}\}, where a_0 = a_{n+1} = +∞. An array is said to be a permutation of integers 1 to n, if it contains all integers from 1 to n exactly once.

Initially, you are only given the value of n without any other information about this permutation.

At each interactive step, you are allowed to choose any i (1 ≤ i ≤ n) and make a query with it. As a response, you will be given the value of a_i. 

You are asked to find any index k which is a local minimum after at most 100 queries.

Interaction

You begin the interaction by reading an integer n (1≤ n ≤ 10^5) on a separate line.

To make a query on index i (1 ≤ i ≤ n), you should output "? i" in a separate line. Then read the value of a_i in a separate line. The number of the "?" queries is limited within 100.

When you find an index k (1 ≤ k ≤ n) which is a local minimum, output "! k" in a separate line and terminate your program. 

In case your query format is invalid, or you have made more than 100 "?" queries, you will receive Wrong Answer verdict. 

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see documentation for other languages.



Hack Format

The first line of the hack should contain a single integer n (1 ≤ n ≤ 10^5).

The second line should contain n distinct integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n).

Example

Input


5
3
2
1
4
5


Output


? 1
? 2
? 3
? 4
? 5
! 3

Note

In the example, the first line contains an integer 5 indicating that the length of the array is n = 5.

The example makes five "?" queries, after which we conclude that the array is a = [3,2,1,4,5] and k = 3 is local minimum.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Think of New York as a rectangular grid consisting of N vertical avenues numerated from 1 to N and M horizontal streets numerated 1 to M. C friends are staying at C hotels located at some street-avenue crossings. They are going to celebrate birthday of one of them in the one of H restaurants also located at some street-avenue crossings. They also want that the maximum distance covered by one of them while traveling to the restaurant to be minimum possible. Help friends choose optimal restaurant for a celebration.

Suppose that the distance between neighboring crossings are all the same equal to one kilometer.


-----Input-----

The first line contains two integers N и M — size of the city (1 ≤ N, M ≤ 10^9). In the next line there is a single integer C (1 ≤ C ≤ 10^5) — the number of hotels friends stayed at. Following C lines contain descriptions of hotels, each consisting of two coordinates x and y (1 ≤ x ≤ N, 1 ≤ y ≤ M). The next line contains an integer H — the number of restaurants (1 ≤ H ≤ 10^5). Following H lines contain descriptions of restaurants in the same format.

Several restaurants and hotels may be located near the same crossing.


-----Output-----

In the first line output the optimal distance. In the next line output index of a restaurant that produces this optimal distance. If there are several possibilities, you are allowed to output any of them.


-----Examples-----
Input
10 10
2
1 1
3 3
2
1 10
4 4

Output
6
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call a non-empty sequence of positive integers a_1, a_2... a_{k} coprime if the greatest common divisor of all elements of this sequence is equal to 1.

Given an array a consisting of n positive integers, find the number of its coprime subsequences. Since the answer may be very large, print it modulo 10^9 + 7.

Note that two subsequences are considered different if chosen indices are different. For example, in the array [1, 1] there are 3 different subsequences: [1], [1] and [1, 1].


-----Input-----

The first line contains one integer number n (1 ≤ n ≤ 100000).

The second line contains n integer numbers a_1, a_2... a_{n} (1 ≤ a_{i} ≤ 100000).


-----Output-----

Print the number of coprime subsequences of a modulo 10^9 + 7.


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

Output
5

Input
4
1 1 1 1

Output
15

Input
7
1 3 5 15 3 105 35

Output
100



-----Note-----

In the first example coprime subsequences are:   1  1, 2  1, 3  1, 2, 3  2, 3 

In the second example all subsequences are coprime.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Night clubs aren’t what they used to be. Our benevolent state has decided that, for health and safety reasons, every club must now meet a minimum lighting standard. They have moved to verify standards by dividing each club up into $1\text { m}^2$ cells and measuring the light levels on the floor with probes in the centre of each cell.

Club owners aren’t happy about this; they will comply with the letter of the law, but don’t want to spend a penny more than they have to on electricity. Instead of upgrading their lighting, they will fence off the offending parts of the club to deal with later.

You will be given a grid representing a map of the lights in a club. Each cell of the grid ($r, c$) will have a light directly above its centre with a bulb of strength $s$, ($0 \le s \le 9$).

The ceiling is flat—its height is constant. Each light will affect every other cell, increasing the light level at distance $(x,y,z)$ by:\[ \frac{s}{x^2+y^2+z^2} \]

Building a section of transparent fencing between any two cells usually costs £11. However, if the cells on both sides meet the minimum lighting standard, the price per length of fencing rises steeply to £43, as builders find it hard to work under the pulsating night club lights and demand extra compensation.

Of course, building a fence along the outside of the clubbing area would not do, as that could block fire exits and cause a whole other kind of hazard.

How much will you have to spend on fencing out the dark spots?

-----Input-----
 - One line containing an integer $B$ ($0 < B \le 9$), the minimum required light level.
 - One line containing an integer $H$ ($0 < H \le 5$), the height of the ceiling in the club.
 - One line containing two integers $R$ and $C$ ($0 < R,C \le 30$), the length and width of the club.
 - $R$ further lines, each containing a string of $C$ digits, representing the strength of lights at each cell of the club.

It is guaranteed that the $2(R+C)-4$ cells along the borders of the club are sufficiently lit.

-----Output-----
 - One line containing one integer: the total number of pounds that must be spent on fencing.

-----Examples-----
Sample Input:
9
1
6 6
333333
300003
300003
300003
300003
333333
Sample Output:
176

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Very soon Berland will hold a School Team Programming Olympiad. From each of the m Berland regions a team of two people is invited to participate in the olympiad. The qualifying contest to form teams was held and it was attended by n Berland students. There were at least two schoolboys participating from each of the m regions of Berland. The result of each of the participants of the qualifying competition is an integer score from 0 to 800 inclusive.

The team of each region is formed from two such members of the qualifying competition of the region, that none of them can be replaced by a schoolboy of the same region, not included in the team and who received a greater number of points. There may be a situation where a team of some region can not be formed uniquely, that is, there is more than one school team that meets the properties described above. In this case, the region needs to undertake an additional contest. The two teams in the region are considered to be different if there is at least one schoolboy who is included in one team and is not included in the other team. It is guaranteed that for each region at least two its representatives participated in the qualifying contest.

Your task is, given the results of the qualifying competition, to identify the team from each region, or to announce that in this region its formation requires additional contests.


-----Input-----

The first line of the input contains two integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 10 000, n ≥ 2m) — the number of participants of the qualifying contest and the number of regions in Berland.

Next n lines contain the description of the participants of the qualifying contest in the following format: Surname (a string of length from 1 to 10 characters and consisting of large and small English letters), region number (integer from 1 to m) and the number of points scored by the participant (integer from 0 to 800, inclusive).

It is guaranteed that all surnames of all the participants are distinct and at least two people participated from each of the m regions. The surnames that only differ in letter cases, should be considered distinct.


-----Output-----

Print m lines. On the i-th line print the team of the i-th region — the surnames of the two team members in an arbitrary order, or a single character "?" (without the quotes) if you need to spend further qualifying contests in the region.


-----Examples-----
Input
5 2
Ivanov 1 763
Andreev 2 800
Petrov 1 595
Sidorov 1 790
Semenov 2 503

Output
Sidorov Ivanov
Andreev Semenov

Input
5 2
Ivanov 1 800
Andreev 2 763
Petrov 1 800
Sidorov 1 800
Semenov 2 503

Output
?
Andreev Semenov



-----Note-----

In the first sample region teams are uniquely determined.

In the second sample the team from region 2 is uniquely determined and the team from region 1 can have three teams: "Petrov"-"Sidorov", "Ivanov"-"Sidorov", "Ivanov" -"Petrov", so it is impossible to determine a team uniquely.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Snacktower

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
According to an old legeng, a long time ago Ankh-Morpork residents did something wrong to miss Fortune, and she cursed them. She said that at some time *n* snacks of distinct sizes will fall on the city, and the residents should build a Snacktower of them by placing snacks one on another. Of course, big snacks should be at the bottom of the tower, while small snacks should be at the top.

Years passed, and once different snacks started to fall onto the city, and the residents began to build the Snacktower.

However, they faced some troubles. Each day exactly one snack fell onto the city, but their order was strange. So, at some days the residents weren't able to put the new stack on the top of the Snacktower: they had to wait until all the bigger snacks fell. Of course, in order to not to anger miss Fortune again, the residents placed each snack on the top of the tower immediately as they could do it.

Write a program that models the behavior of Ankh-Morpork residents.

Input Specification:
The first line contains single integer *n* (1<=≤<=*n*<=≤<=100<=000) — the total number of snacks.

The second line contains *n* integers, the *i*-th of them equals the size of the snack which fell on the *i*-th day. Sizes are distinct integers from 1 to *n*.

Output Specification:
Print *n* lines. On the *i*-th of them print the sizes of the snacks which the residents placed on the top of the Snacktower on the *i*-th day in the order they will do that. If no snack is placed on some day, leave the corresponding line empty.

Demo Input:
['3\n3 1 2\n', '5\n4 5 1 2 3\n']

Demo Output:
['3\n\xa0\n2 1', '5 4\n\xa0\n\xa0\n3 2 1\n']

Note:
In the example a snack of size 3 fell on the first day, and the residents immediately placed it. On the second day a snack of size 1 fell, and the residents weren't able to place it because they were missing the snack of size 2. On the third day a snack of size 2 fell, and the residents immediately placed it. Right after that they placed the snack of size 1 which had fallen before.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice is playing with some stones.

Now there are three numbered heaps of stones. The first of them contains $a$ stones, the second of them contains $b$ stones and the third of them contains $c$ stones.

Each time she can do one of two operations:  take one stone from the first heap and two stones from the second heap (this operation can be done only if the first heap contains at least one stone and the second heap contains at least two stones);  take one stone from the second heap and two stones from the third heap (this operation can be done only if the second heap contains at least one stone and the third heap contains at least two stones). 

She wants to get the maximum number of stones, but she doesn't know what to do. Initially, she has $0$ stones. Can you help her?


-----Input-----

The first line contains one integer $t$ ($1 \leq t \leq 100$)  — the number of test cases. Next $t$ lines describe test cases in the following format:

Line contains three non-negative integers $a$, $b$ and $c$, separated by spaces ($0 \leq a,b,c \leq 100$) — the number of stones in the first, the second and the third heap, respectively.

In hacks it is allowed to use only one test case in the input, so $t = 1$ should be satisfied.


-----Output-----

Print $t$ lines, the answers to the test cases in the same order as in the input. The answer to the test case is the integer  — the maximum possible number of stones that Alice can take after making some operations. 


-----Example-----
Input
3
3 4 5
1 0 5
5 3 2

Output
9
0
6



-----Note-----

For the first test case in the first test, Alice can take two stones from the second heap and four stones from the third heap, making the second operation two times. Then she can take one stone from the first heap and two stones from the second heap, making the first operation one time. The summary number of stones, that Alice will take is $9$. It is impossible to make some operations to take more than $9$ stones, so the answer is $9$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N voting papers. The i-th vote (1 \leq i \leq N) has the string S_i written on it.
Print all strings that are written on the most number of votes, in lexicographical order.

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - S_i (1 \leq i \leq N) are strings consisting of lowercase English letters.
 - The length of S_i (1 \leq i \leq N) is between 1 and 10 (inclusive).

-----Input-----
Input is given from Standard Input in the following format:
N
S_1
:
S_N

-----Output-----
Print all strings in question in lexicographical order.

-----Sample Input-----
7
beat
vet
beet
bed
vet
bet
beet

-----Sample Output-----
beet
vet

beet and vet are written on two sheets each, while beat, bed, and bet are written on one vote each. Thus, we should print the strings beet and vet.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.