vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A couple of friends, Axel and Marston are travelling across the country of Bitland. There are n towns in Bitland, with some pairs of towns connected by one-directional roads. Each road in Bitland is either a pedestrian road or a bike road. There can be multiple roads between any pair of towns, and may even be a road from a town to itself. However, no pair of roads shares the starting and the destination towns along with their types simultaneously.

The friends are now located in the town 1 and are planning the travel route. Axel enjoys walking, while Marston prefers biking. In order to choose a route diverse and equally interesting for both friends, they have agreed upon the following procedure for choosing the road types during the travel:

  * The route starts with a pedestrian route.
  * Suppose that a beginning of the route is written in a string s of letters P (pedestrain road) and B (biking road). Then, the string <image> is appended to s, where <image> stands for the string s with each character changed to opposite (that is, all pedestrian roads changed to bike roads, and vice versa).



In the first few steps the route will look as follows: P, PB, PBBP, PBBPBPPB, PBBPBPPBBPPBPBBP, and so on.

After that the friends start travelling from the town 1 via Bitlandian roads, choosing the next road according to the next character of their route type each time. If it is impossible to choose the next road, the friends terminate their travel and fly home instead.

Help the friends to find the longest possible route that can be travelled along roads of Bitland according to the road types choosing procedure described above. If there is such a route with more than 1018 roads in it, print -1 instead.

Input

The first line contains two integers n and m (1 ≤ n ≤ 500, 0 ≤ m ≤ 2n2) — the number of towns and roads in Bitland respectively.

Next m lines describe the roads. i-th of these lines contains three integers vi, ui and ti (1 ≤ vi, ui ≤ n, 0 ≤ ti ≤ 1), where vi and ui denote start and destination towns indices of the i-th road, and ti decribes the type of i-th road (0 for a pedestrian road, 1 for a bike road). It is guaranteed that for each pair of distinct indices i, j such that 1 ≤ i, j ≤ m, either vi ≠ vj, or ui ≠ uj, or ti ≠ tj holds.

Output

If it is possible to find a route with length strictly greater than 1018, print -1. Otherwise, print the maximum length of a suitable path.

Examples

Input

2 2
1 2 0
2 2 1


Output

3


Input

2 3
1 2 0
2 2 1
2 2 0


Output

-1

Note

In the first sample we can obtain a route of length 3 by travelling along the road 1 from town 1 to town 2, and then following the road 2 twice from town 2 to itself.

In the second sample we can obtain an arbitrarily long route by travelling the road 1 first, and then choosing road 2 or 3 depending on the necessary type.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A squarer is a simple and convenient device. You give it some positive integer X and it calculates its square.
Leha is implementing a module of this device which is responsible for squaring the numbers consisting of multiple repetitions of one digit. But it turned out that it's not as simple as he thought.
Please help him now!

-----Input-----
The first line contains one integer T denoting the number of testcases. The descriptions of T test cases follow.
Each of the following T lines contain 2 space-separated integers - N and D, respectively. It means that the number X in the corresponding testcase consists of the digit D repeated N times (in decimal representation).

-----Output-----
As the answer can be very large, we ask you to output its hash which is computed in the following way:
Let's consider the integer answer Y as a 0-indexed array starting from its leftmost digit. The hash function is calculated as:
p0*Y[0] + p1*Y[1] + ... + pM-1*Y[M-1] modulo 109 + 7 
where M is the length of the array representation of Y and p equals 23.

-----Constraints-----
- 1 ≤ T ≤ 20
- 1 ≤ D ≤ 9
- Subtask 1 (16 points): 1 ≤ N ≤ 9
- Subtask 2 (25 points): 1 ≤ N ≤ 100
- Subtask 3 (27 points): 1 ≤ N ≤ 2 × 104
- Subtask 4 (32 points): 1 ≤ N ≤ 106

-----Example-----
Input:3
1 4
3 6
3 5

Output:139
40079781
32745632

-----Explanation-----
In the first test case, X = 4 and Y = 16. Its hash equals 1*1 + 23*6 = 139.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n integers a1, a2, ..., an. Denote this list of integers as T.

Let f(L) be a function that takes in a non-empty list of integers L.

The function will output another integer as follows: 

  * First, all integers in L are padded with leading zeros so they are all the same length as the maximum length number in L. 
  * We will construct a string where the i-th character is the minimum of the i-th character in padded input numbers. 
  * The output is the number representing the string interpreted in base 10. 



For example f(10, 9) = 0, f(123, 321) = 121, f(530, 932, 81) = 30.

Define the function 

<image> Here, <image> denotes a subsequence.

In other words, G(x) is the sum of squares of sum of elements of nonempty subsequences of T that evaluate to x when plugged into f modulo 1 000 000 007, then multiplied by x. The last multiplication is not modded. 

You would like to compute G(0), G(1), ..., G(999 999). To reduce the output size, print the value <image>, where <image> denotes the bitwise XOR operator.

Input

The first line contains the integer n (1 ≤ n ≤ 1 000 000) — the size of list T.

The next line contains n space-separated integers, a1, a2, ..., an (0 ≤ ai ≤ 999 999) — the elements of the list. 

Output

Output a single integer, the answer to the problem.

Examples

Input

3
123 321 555


Output

292711924


Input

1
999999


Output

997992010006992


Input

10
1 1 1 1 1 1 1 1 1 1


Output

28160

Note

For the first sample, the nonzero values of G are G(121) = 144 611 577, G(123) = 58 401 999, G(321) = 279 403 857, G(555) = 170 953 875. The bitwise XOR of these numbers is equal to 292 711 924.

For example, <image>, since the subsequences [123] and [123, 555] evaluate to 123 when plugged into f.

For the second sample, we have <image>

For the last sample, we have <image>, where <image> is the binomial coefficient.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N children in AtCoder Kindergarten. Mr. Evi will arrange the children in a line, then give 1 candy to the first child in the line, 2 candies to the second child, ..., N candies to the N-th child. How many candies will be necessary in total?

-----Constraints-----
 - 1≦N≦100

-----Input-----
The input is given from Standard Input in the following format:
N

-----Output-----
Print the necessary number of candies in total.

-----Sample Input-----
3

-----Sample Output-----
6

The answer is 1+2+3=6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a number of sticks of varying lengths.  You will iteratively cut the sticks into smaller sticks, discarding the shortest pieces until there are none left.  At each iteration you will determine the length of the shortest stick remaining, cut that length from each of the longer sticks and then discard all the pieces of that shortest length.  When all the remaining sticks are the same length, they cannot be shortened so discard them.

Given the lengths of $n$ sticks, print the number of sticks that are left before each iteration until there are none left.

Example 

$arr=[1,2,3]$   

The shortest stick length is $1$, so cut that length from the longer two and discard the pieces of length $1$.  Now the lengths are $arr=[1,2]$.  Again, the shortest stick is of length $1$, so cut that amount from the longer stick and discard those pieces.  There is only one stick left, $arr=[1]$, so discard that stick.  The number of sticks at each iteration are $answer=[3,2,1]$.  

Function Description  

Complete the cutTheSticks function in the editor below.  It should return an array of integers representing the number of sticks before each cut operation is performed.  

cutTheSticks has the following parameter(s):  

int arr[n]: the lengths of each stick  

Returns  

int[]:  the number of sticks after each iteration  

Input Format  

The first line contains a single integer $n$, the size of $\textbf{arr}$. 

The next line contains $n$ space-separated integers, each an $arr\left[i\right]$, where each value represents the length of the $i^{\mbox{th}}$ stick.  

Constraints  

$1\leq n\leq1000$
$1\leq arr[i]\leq1000$

Sample Input 0

STDIN           Function
-----           --------
6               arr[] size n = 6
5 4 4 2 2 8     arr = [5, 4, 4, 2, 2, 8]

Sample Output 0

6
4
2
1

Explanation 0

sticks-length        length-of-cut   sticks-cut
5 4 4 2 2 8             2               6
3 2 2 _ _ 6             2               4
1 _ _ _ _ 4             1               2
_ _ _ _ _ 3             3               1
_ _ _ _ _ _           DONE            DONE

Sample Input 1

8
1 2 3 4 3 3 2 1

Sample Output 1

8
6
4
1

Explanation 1

sticks-length         length-of-cut   sticks-cut
1 2 3 4 3 3 2 1         1               8
_ 1 2 3 2 2 1 _         1               6
_ _ 1 2 1 1 _ _         1               4
_ _ _ 1 _ _ _ _         1               1
_ _ _ _ _ _ _ _       DONE            DONE

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
itertools.product()

This tool computes the cartesian product of input iterables. 

It is equivalent to nested for-loops. 

For example, product(A, B) returns the same as ((x,y) for x in A for y in B).  

Sample Code

>>> from itertools import product
>>>
>>> print list(product([1,2,3],repeat = 2))
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
>>>
>>> print list(product([1,2,3],[3,4]))
[(1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4)]
>>>
>>> A = [[1,2,3],[3,4,5]]
>>> print list(product(*A))
[(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 3), (3, 4), (3, 5)]
>>>
>>> B = [[1,2,3],[3,4,5],[7,8]]
>>> print list(product(*B))
[(1, 3, 7), (1, 3, 8), (1, 4, 7), (1, 4, 8), (1, 5, 7), (1, 5, 8), (2, 3, 7), (2, 3, 8), (2, 4, 7), (2, 4, 8), (2, 5, 7), (2, 5, 8), (3, 3, 7), (3, 3, 8), (3, 4, 7), (3, 4, 8), (3, 5, 7), (3, 5, 8)]

Task

You are given a two lists $\mbox{A}$ and $\mbox{B}$. Your task is to compute their cartesian product $\mbox{A}$X$\mbox{B}$.

Example  

A = [1, 2]
B = [3, 4]

AxB = [(1, 3), (1, 4), (2, 3), (2, 4)]

Note: $\mbox{A}$ and $\mbox{B}$ are sorted lists, and the cartesian product's tuples should be output in sorted order.

Input Format

The first line contains the space separated elements of list $\mbox{A}$. 

The second line contains the space separated elements of list $\mbox{B}$.

Both lists have no duplicate integer elements.

Constraints

$0<A<30$ 

  $0<B<30$

Output Format

Output the space separated tuples of the cartesian product.

Sample Input
 1 2
 3 4

Sample Output
 (1, 3) (1, 4) (2, 3) (2, 4)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shaass has n books. He wants to make a bookshelf for all his books. He wants the bookshelf's dimensions to be as small as possible. The thickness of the i-th book is t_{i} and its pages' width is equal to w_{i}. The thickness of each book is either 1 or 2. All books have the same page heights. $1$ 

Shaass puts the books on the bookshelf in the following way. First he selects some of the books and put them vertically. Then he puts the rest of the books horizontally above the vertical books. The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books. A sample arrangement of the books is depicted in the figure. [Image] 

Help Shaass to find the minimum total thickness of the vertical books that we can achieve.


-----Input-----

The first line of the input contains an integer n, (1 ≤ n ≤ 100). Each of the next n lines contains two integers t_{i} and w_{i} denoting the thickness and width of the i-th book correspondingly, (1 ≤ t_{i} ≤ 2, 1 ≤ w_{i} ≤ 100).


-----Output-----

On the only line of the output print the minimum total thickness of the vertical books that we can achieve.


-----Examples-----
Input
5
1 12
1 3
2 15
2 5
2 1

Output
5

Input
3
1 10
2 1
2 4

Output
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

You are given a sequence A_{1}, A_{2}, ..., A_{N} and Q queries. In each query, you are given two parameters L and R; you have to find the smallest integer X such that 0 ≤ X < 2^{31} and the value of (A_{L} xor X) + (A_{L+1} xor X) + ... + (A_{R} xor X) is maximum possible.

Note: xor denotes the bitwise xor operation.

------ Input ------ 

The first line of the input contains two space-separated integers N and Q denoting the number of elements in A and the number of queries respectively.
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N}.
Each of the next Q lines contains two space-separated integers L and R describing one query.

------ Output ------ 

For each query, print a single line containing one integer — the minimum value of X. 

------ Constraints ------ 

$1 ≤ N ≤ 10^{5}$
$1 ≤ Q ≤ 10^{5}$
$0 ≤ A_{i} < 2^{31} for each valid i$

------ Subtasks ------ 

Subtask #1 (18 points):

$1 ≤ N ≤ 10^{3}$
$1 ≤ Q ≤ 10^{3}$
$0 ≤ A_{i} < 2^{10} for each valid i$

Subtask #2 (82 points): original constraints

----- Sample Input 1 ------ 
5 3

20 11 18 2 13

1 3

3 5

2 4
----- Sample Output 1 ------ 
2147483629

2147483645

2147483645

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The famous sculptor Cicasso is a Reberlandian spy!

These is breaking news in Berlandian papers today. And now the sculptor is hiding. This time you give the shelter to the maestro. You have a protected bunker and you provide it to your friend. You set the security system in such way that only you can open the bunker. To open it one should solve the problem which is hard for others but is simple for you.

Every day the bunker generates a codeword s. Every time someone wants to enter the bunker, integer n appears on the screen. As the answer one should enter another integer — the residue modulo 109 + 7 of the number of strings of length n that consist only of lowercase English letters and contain the string s as the subsequence.

The subsequence of string a is a string b that can be derived from the string a by removing some symbols from it (maybe none or all of them). In particular any string is the subsequence of itself. For example, the string "cfo" is the subsequence of the string "codeforces".

You haven't implemented the algorithm that calculates the correct answers yet and you should do that ASAP.

Input

The first line contains integer m (1 ≤ m ≤ 105) — the number of the events in the test case.

The second line contains nonempty string s — the string generated by the bunker for the current day.

The next m lines contain the description of the events. The description starts from integer t — the type of the event.

If t = 1 consider a new day has come and now a new string s is used. In that case the same line contains a new value of the string s.

If t = 2 integer n is given (1 ≤ n ≤ 105). This event means that it's needed to find the answer for the current string s and the value n.

The sum of lengths of all generated strings doesn't exceed 105. All of the given strings consist only of lowercase English letters.

Output

For each query of the type 2 print the answer modulo 109 + 7 on the separate line.

Example

Input

3
a
2 2
1 bc
2 5


Output

51
162626

Note

In the first event words of the form "a?" and "?a" are counted, where ? is an arbitrary symbol. There are 26 words of each of these types, but the word "aa" satisfies both patterns, so the answer is 51.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Dima loves representing an odd number as the sum of multiple primes, and Lisa loves it when there are at most three primes. Help them to represent the given number as the sum of at most than three primes.

More formally, you are given an odd numer *n*. Find a set of numbers *p**i* (1<=≤<=*i*<=≤<=*k*), such that
1.  1<=≤<=*k*<=≤<=31.  *p**i* is a prime1.  
The numbers *p**i* do not necessarily have to be distinct. It is guaranteed that at least one possible solution exists.

Input Specification:
The single line contains an odd number *n* (3<=≤<=*n*<=&lt;<=109).

Output Specification:
In the first line print *k* (1<=≤<=*k*<=≤<=3), showing how many numbers are in the representation you found.

In the second line print numbers *p**i* in any order. If there are multiple possible solutions, you can print any of them.

Demo Input:
['27\n']

Demo Output:
['3\n5 11 11\n']

Note:
A prime is an integer strictly larger than one that is divisible only by one and by itself.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Oh no! Joanna just spilled some syrup on her keyboard and now some of the keys are sticky. This causes her considerable frustration, as every time she presses one of the sticky keys, the corresponding character gets entered twice on her computer. 

This could not have happened at a more inconvenient time; it is the start of the contest and she was just about to type in the solution to the first problem! Joanna does not have time to remove and clean every key on her keyboard, so she wonders if there is a way to quickly identify the sticky keys. Starting to panic, she quickly types some text on her keyboard and stares at the resulting text displayed on her screen.

Given the line of text that Joanna typed on her keyboard and the resulting text displayed on her screen, help her determine which keys must be sticky.

-----Input-----
The input consists of:
 - One line containing a string $s$ ($1 \leq \mathrm{length}(s) \leq 1000$), the text that Joanna typed on her keyboard.
 - One line containing a string $t$ ($1 \leq \mathrm{length}(t) \leq 1000$), the text displayed on Joanna’s screen as a result.

Both $s$ and $t$ consist only of lower-case letters (‘a’–‘z’) and spaces (‘ ’), and start and end with a letter.

It is guaranteed that $t$ is the result of doubling each character in $s$ that corresponds to a sticky key. At least one character in $s$ corresponds to a sticky key (i.e. $s \neq t$).

-----Output-----
Output all characters (letters and space) corresponding to keys that must be sticky, in any order.

-----Examples-----
Sample Input:
this is very annoying
thiss iss veery annoying
Sample Output:
se

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Once Algorithm guru gave a simple problem to his students.He gave a list of n integers say, A={a1,a2,a3...an} and another integer, x representing the expected sum.
He said students to select numbers from array list(0 or more numbers) such that the sum of these numbers is as close as possible but not exceeding to the sum x.

Note:Each element of A can be selected multiple times.If no element is selected then the sum is 0.

Input Format:

The first line contains T the number of test cases. 
Each test case is followed by two lines. First line contains two integers n,x, representing the length of list A and expected sum.
Second line consists of n space separated integers, a1,a2,…,an, representing the elements of list A.

Output Format:

Output T lines, the maximum sum for each test case which is as near as possible, but not exceeding, to the expected sum x.

Constraints:

1≤T≤10 

1≤n≤3000 

1≤x≤3000 

1≤ai≤3000,(1 ≤ i ≤ n)

SAMPLE INPUT
2
3 12
1 6 9
5 9
3 4 4 4 8

SAMPLE OUTPUT
12
9

Explanation

In the first test case, one can pick {6, 6}. 
In the second, we can pick {3,3,3}
Register for IndiaHacks

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've got an *n*<=×<=*m* pixel picture. Each pixel can be white or black. Your task is to change the colors of as few pixels as possible to obtain a barcode picture.

A picture is a barcode if the following conditions are fulfilled: 
 -  All pixels in each column are of the same color. -  The width of each monochrome vertical line is at least *x* and at most *y* pixels. In other words, if we group all neighbouring columns of the pixels with equal color, the size of each group can not be less than *x* or greater than *y*.

Input Specification:
The first line contains four space-separated integers *n*, *m*, *x* and *y* (1<=≤<=*n*,<=*m*,<=*x*,<=*y*<=≤<=1000; *x*<=≤<=*y*).

Then follow *n* lines, describing the original image. Each of these lines contains exactly *m* characters. Character "." represents a white pixel and "#" represents a black pixel. The picture description doesn't have any other characters besides "." and "#".

Output Specification:
In the first line print the minimum number of pixels to repaint. It is guaranteed that the answer exists.

Demo Input:
['6 5 1 2\n##.#.\n.###.\n###..\n#...#\n.##.#\n###..\n', '2 5 1 1\n#####\n.....\n']

Demo Output:
['11\n', '5\n']

Note:
In the first test sample the picture after changing some colors can looks as follows: 

In the second test sample the picture after changing some colors can looks as follows:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In late autumn evening n robots gathered in the cheerful company of friends. Each robot has a unique identifier — an integer from 1 to 10^9.

At some moment, robots decided to play the game "Snowball". Below there are the rules of this game. First, all robots stand in a row. Then the first robot says his identifier. After that the second robot says the identifier of the first robot and then says his own identifier. Then the third robot says the identifier of the first robot, then says the identifier of the second robot and after that says his own. This process continues from left to right until the n-th robot says his identifier.

Your task is to determine the k-th identifier to be pronounced.


-----Input-----

The first line contains two positive integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ min(2·10^9, n·(n + 1) / 2).

The second line contains the sequence id_1, id_2, ..., id_{n} (1 ≤ id_{i} ≤ 10^9) — identifiers of roborts. It is guaranteed that all identifiers are different.


-----Output-----

Print the k-th pronounced identifier (assume that the numeration starts from 1).


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

Output
1

Input
4 5
10 4 18 3

Output
4



-----Note-----

In the first sample identifiers of robots will be pronounced in the following order: 1, 1, 2. As k = 2, the answer equals to 1.

In the second test case identifiers of robots will be pronounced in the following order: 10, 10, 4, 10, 4, 18, 10, 4, 18, 3. As k = 5, the answer equals to 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array containing only integers, add all the elements and return the binary equivalent of that sum.

If the array contains any non-integer element (e.g. an object, a float, a string and so on), return false.

**Note:** The sum of an empty array is zero.

```python
arr2bin([1,2]) == '11'
arr2bin([1,2,'a']) == False
```

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