vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Archeologists recently found the remains of Greco-Roman architecture. The location can be modeled as a grid of $R \cdot C$ square cells. For each of the cells, archeologists have determined if some building was there or if the cell has always been empty.

After examining the artifacts in detail, they concluded that the location contains two buildings from different periods in time, and that the floor plans of both buildings are of square shape.

Because the buildings were from different periods in time, it is possible that their floor plans overlap. Determine the possible location and size (length of the side of the square occupied by the floor plan) for each building.

-----Input-----
The first line contains two integers $R$ ($1 \le R \le 100$) and $C$ ($1 \le C \le 100$), the size of the location.

Each of the next $R$ lines contains a string of $C$ characters ‘.’ (dot) or ‘x’ (lowercase letter). The character ‘.’ means that nothing was found in that cell, while ‘x’ indicates that there was a building there.

-----Output-----
For each of the two buildings, output on a single line the row and column of its upper left corner, and the size (side length) of the building.

Note: the test data will be such that a solution always exists, although it may not be unique. If there is more than one solution, any one will be accepted.

-----Examples-----
Sample Input 1:
3 3
xx.
xxx
...
Sample Output 1:
1 1 2
2 3 1

Sample Input 2:
4 6
xx....
xx.xxx
...xxx
...xxx
Sample Output 2:
1 1 2
2 4 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer sequence of length n+1, a_1,a_2,...,a_{n+1}, which consists of the n integers 1,...,n.
It is known that each of the n integers 1,...,n appears at least once in this sequence.
For each integer k=1,...,n+1, find the number of the different subsequences (not necessarily contiguous) of the given sequence with length k, modulo 10^9+7.

-----Notes-----
 - If the contents of two subsequences are the same, they are not separately counted even if they originate from different positions in the original sequence.
 - A subsequence of a sequence a with length k is a sequence obtained by selecting k of the elements of a and arranging them without changing their relative order. For example, the sequences 1,3,5 and 1,2,3 are subsequences of 1,2,3,4,5, while 3,1,2 and 1,10,100 are not.

-----Constraints-----
 - 1 \leq n \leq 10^5
 - 1 \leq a_i \leq n
 - Each of the integers 1,...,n appears in the sequence.
 - n and a_i are integers.

-----Input-----
Input is given from Standard Input in the following format:
n
a_1 a_2 ... a_{n+1}

-----Output-----
Print n+1 lines.
The k-th line should contain the number of the different subsequences of the given sequence with length k, modulo 10^9+7.

-----Sample Input-----
3
1 2 1 3

-----Sample Output-----
3
5
4
1

There are three subsequences with length 1: 1 and 2 and 3.
There are five subsequences with length 2: 1,1 and 1,2 and 1,3 and 2,1 and 2,3.
There are four subsequences with length 3: 1,1,3 and 1,2,1 and 1,2,3 and 2,1,3.
There is one subsequence with length 4: 1,2,1,3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given A, B, and C as the sides of a triangle, find whether the triangle is *scalene*.

Note:
A triangle is said to be *scalene* if all three sides of the triangle are distinct.
It is guaranteed that the sides represent a valid triangle.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of three space-separated integers A, B, and C — the length of the three sides of the triangle.

------ Output Format ------ 

For each test case, output on a new line, YES, if the triangle is *scalene*, and NO otherwise.

You may print each character of the string in uppercase or lowercase. For example, YES, yes, Yes, and yEs are all considered identical.

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

$1 ≤ T ≤ 100$
$1 ≤ A ≤B ≤C ≤ 10$
$C < (A+B)$

----- Sample Input 1 ------ 
4
2 3 4
1 2 2
2 2 2
3 5 6

----- Sample Output 1 ------ 
YES
NO
NO
YES
----- explanation 1 ------ 
Test case $1$: The side lengths are $2, 3, $ and $4$. Since no two side lengths are equal, the triangle is scalene.

Test case $2$: The side lengths are $1, 2, $ and $2$. The sides $B$ and $C$ have the same length. Thus, the triangle is not scalene.

Test case $3$: The side lengths are $2, 2, $ and $2$. The sides $A, B,$ and $C$ have the same length. Thus, the triangle is not scalene.

Test case $4$: The side lengths are $3, 5, $ and $6$. Since no two side lengths are equal, the triangle is scalene.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A ticket is a string consisting of six digits. A ticket is considered lucky if the sum of the first three digits is equal to the sum of the last three digits. Given a ticket, output if it is lucky or not. Note that a ticket can have leading zeroes.


-----Input-----

The first line of the input contains an integer $t$ ($1 \leq t \leq 10^3$) — the number of testcases.

The description of each test consists of one line containing one string consisting of six digits.


-----Output-----

Output $t$ lines, each of which contains the answer to the corresponding test case. Output "YES" if the given ticket is lucky, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).


-----Examples-----

Input
5
213132
973894
045207
000000
055776
Output
YES
NO
YES
YES
NO


-----Note-----

In the first test case, the sum of the first three digits is $2 + 1 + 3 = 6$ and the sum of the last three digits is $1 + 3 + 2 = 6$, they are equal so the answer is "YES".

In the second test case, the sum of the first three digits is $9 + 7 + 3 = 19$ and the sum of the last three digits is $8 + 9 + 4 = 21$, they are not equal so the answer is "NO".

In the third test case, the sum of the first three digits is $0 + 4 + 5 = 9$ and the sum of the last three digits is $2 + 0 + 7 = 9$, they are equal so the answer is "YES".

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

Probably, you have already read some problems but you still have not met any problems with queries on segments. Therefore Benny wants to fix it.

She gives you an array A of N elements.  And then you have to answer Q queries.

Each query consists of three integers L, R, X. Your task is to find such Ai, that L ≤ i ≤ R and Ai xor X is maximal. For each query output the maximum of Ai xor X.

Input format

The first line contains two integers N and Q.
The next line contains N integers Ai.
The next Q lines contain three integers L, R, X.

Output format

For each query output the maximum of Ai xor X in a single line.

Constraints
1 ≤ N, Q ≤ 5 * 10^5
0 ≤ Ai < 2^20
1 ≤ L ≤ R ≤ N
0 ≤ X < 2^20
1 ≤ N, Q ≤ 3 * 10^3 holds for test cases worth 15% of the problem's score.
1 ≤ N, Q ≤ 10^5 holds for test cases worth 60% of the problem's score.

SAMPLE INPUT
5 3
1 7 3 8 2
1 5 10
3 4 6
2 5 8

SAMPLE OUTPUT
13
14
15

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Check Tutorial tab to know how to to solve.  

You are given a string $\mbox{S}$ and width $\boldsymbol{w}$. 

Your task is to wrap the string into a paragraph of width $\boldsymbol{w}$.  

Function Description   

Complete the wrap function in the editor below.  

wrap has the following parameters:   

string string: a long string   
int max_width: the width to wrap to   

Returns   

string: a single string with newline characters ('\n') where the breaks should be   

Input Format

The first line contains a string, $\textit{string}$. 

The second line contains the width, $max_width$.

Constraints

$0<len(string)<1000$  
$0<max_{w}idth<len(string)$

Sample Input 0
ABCDEFGHIJKLIMNOQRSTUVWXYZ
4

Sample Output 0
ABCD
EFGH
IJKL
IMNO
QRST
UVWX
YZ

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
IT City administration has no rest because of the fame of the Pyramids in Egypt. There is a project of construction of pyramid complex near the city in the place called Emerald Walley. The distinction of the complex is that its pyramids will be not only quadrangular as in Egypt but also triangular and pentagonal. Of course the amount of the city budget funds for the construction depends on the pyramids' volume. Your task is to calculate the volume of the pilot project consisting of three pyramids — one triangular, one quadrangular and one pentagonal.

The first pyramid has equilateral triangle as its base, and all 6 edges of the pyramid have equal length. The second pyramid has a square as its base and all 8 edges of the pyramid have equal length. The third pyramid has a regular pentagon as its base and all 10 edges of the pyramid have equal length. [Image] 


-----Input-----

The only line of the input contains three integers l_3, l_4, l_5 (1 ≤ l_3, l_4, l_5 ≤ 1000) — the edge lengths of triangular, quadrangular and pentagonal pyramids correspondingly.


-----Output-----

Output one number — the total volume of the pyramids. Absolute or relative error should not be greater than 10^{ - 9}.


-----Examples-----
Input
2 5 3

Output
38.546168065709

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Boy Dima gave Julian a birthday present — set $B$ consisting of positive integers. However, he didn't know, that Julian hates sets, but enjoys bipartite graphs more than anything else!

Julian was almost upset, but her friend Alex said, that he can build an undirected graph using this set in such a way: let all integer numbers be vertices, then connect any two $i$ and $j$ with an edge if $|i - j|$ belongs to $B$.

Unfortunately, Julian doesn't like the graph, that was built using $B$. Alex decided to rectify the situation, so he wants to erase some numbers from $B$, so that graph built using the new set is bipartite. The difficulty of this task is that the graph, Alex has to work with, has an infinite number of vertices and edges! It is impossible to solve this task alone, so Alex asks you for help. Write a program that erases a subset of minimum size from $B$ so that graph constructed on the new set is bipartite.

Recall, that graph is bipartite if all its vertices can be divided into two disjoint sets such that every edge connects a vertex from different sets.


-----Input-----

First line contains an integer $n ~ (1 \leqslant n \leqslant 200\,000)$ — size of $B$

Second line contains $n$ integers $b_1, b_2, \ldots, b_n ~ (1 \leqslant b_i \leqslant 10^{18})$ — numbers of $B$, all $b_i$ are unique


-----Output-----

In the first line print single integer $k$ – the number of erased elements. In the second line print $k$ integers — values of erased elements.

If there are multiple answers, print any of them.


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

Output
1
2 
Input
2
2 6

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of integers $a_1, a_2, \ldots, a_n$ and an integer $x$.

You need to select the maximum number of elements in the array, such that for every subsegment $a_l, a_{l + 1}, \ldots, a_r$ containing strictly more than one element $(l < r)$, either:

At least one element on this subsegment is not selected, or

$a_l + a_{l+1} + \ldots + a_r \geq x \cdot (r - l + 1)$.


-----Input-----

The first line of input contains one integer $t$ ($1 \leq t \leq 10$): the number of test cases.

The descriptions of $t$ test cases follow, three lines per test case.

In the first line you are given one integer $n$ ($1 \leq n \leq 50000$): the number of integers in the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-100000 \leq a_i \leq 100000$).

The third line contains one integer $x$ ($-100000 \leq x \leq 100000$).


-----Output-----

For each test case, print one integer: the maximum number of elements that you can select.


-----Examples-----

Input
4
5
1 2 3 4 5
2
10
2 4 2 4 2 4 2 4 2 4
3
3
-10 -5 -10
-8
3
9 9 -3
5
Output
4
8
2
2


-----Note-----

In the first example, one valid way to select the elements is $[\underline{1}, 2, \underline{3}, \underline{4}, \underline{5}]$. All subsegments satisfy at least one of the criteria. For example, for the subsegment $l = 1$, $r = 2$ we have that the element $2$ is not selected, satisfying the first criterion. For the subsegment $l = 3$, $r = 5$ we have $3 + 4 + 5 = 12 \ge 2 \cdot 3$, satisfying the second criterion.

We can't select all elements, because in this case for $l = 1$, $r = 2$ all elements are selected and we have $a_1 + a_2 = 3 < 2 \cdot 2$. Thus, the maximum number of selected elements is $4$.

In the second example, one valid solution is $[\underline{2}, \underline{4}, 2, \underline{4}, \underline{2}, \underline{4}, 2, \underline{4}, \underline{2}, \underline{4}]$.

In the third example, one valid solution is $[\underline{-10}, -5, \underline{-10}]$.

In the fourth example, one valid solution is $[\underline{9}, \underline{9}, -3]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Assume that you have $k$ one-dimensional segments $s_1, s_2, \dots s_k$ (each segment is denoted by two integers — its endpoints). Then you can build the following graph on these segments. The graph consists of $k$ vertexes, and there is an edge between the $i$-th and the $j$-th vertexes ($i \neq j$) if and only if the segments $s_i$ and $s_j$ intersect (there exists at least one point that belongs to both of them).

For example, if $s_1 = [1, 6], s_2 = [8, 20], s_3 = [4, 10], s_4 = [2, 13], s_5 = [17, 18]$, then the resulting graph is the following: [Image] 

A tree of size $m$ is good if it is possible to choose $m$ one-dimensional segments so that the graph built on these segments coincides with this tree.

You are given a tree, you have to find its good subtree with maximum possible size. Recall that a subtree is a connected subgraph of a tree.

Note that you have to answer $q$ independent queries.


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 15 \cdot 10^4$) — the number of the queries. 

The first line of each query contains one integer $n$ ($2 \le n \le 3 \cdot 10^5$) — the number of vertices in the tree.

Each of the next $n - 1$ lines contains two integers $x$ and $y$ ($1 \le x, y \le n$) denoting an edge between vertices $x$ and $y$. It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of all $n$ does not exceed $3 \cdot 10^5$.


-----Output-----

For each query print one integer — the maximum size of a good subtree of the given tree.


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

Output
8



-----Note-----

In the first query there is a good subtree of size $8$. The vertices belonging to this subtree are ${9, 4, 10, 2, 5, 1, 6, 3}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Fair Nut has two arrays a and b, consisting of n numbers. He found them so long ago that no one knows when they came to him.

The Fair Nut often changes numbers in his arrays. He also is interested in how similar a and b are after every modification.

Let's denote similarity of two arrays as the minimum number of operations to apply to make arrays equal (every operation can be applied for both arrays). If it is impossible, similarity will be equal -1.

Per one operation you can choose a subarray with length k (k is fixed), and change every element a_i, which belongs to the chosen subarray, to a_i ⊕ x (x can be chosen), where ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 

Nut has already calculated the similarity of the arrays after every modification. Can you do it?

Note that you just need to calculate those values, that is you do not need to apply any operations.

Input

The first line contains three numbers n, k and q (1 ≤ k ≤ n ≤ 2 ⋅ 10^5, 0 ≤ q ≤ 2 ⋅ 10^5) — the length of the arrays, the length of the subarrays, to which the operations are applied, and the number of queries.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i < 2^{14}) — elements of array a.

The third line contains n integers b_1, b_2, …, b_n (0 ≤ b_i < 2^{14}) — elements of array b.

Each of the next q lines describes query and contains string s and two integers p and v (1 ≤ p ≤ n, 0 ≤ v < 2^{14}) — array, which this query changes («a» or «b» without quotes), index of changing element and its new value.

Output

On the first line print initial similarity of arrays a and b.

On the i-th of following q lines print similarity of a and b after applying first i modifications.

Examples

Input

3 3 1
0 4 2
1 2 3
b 2 5


Output

-1
1


Input

3 2 2
1 3 2
0 0 0
a 1 0
b 1 1


Output

2
-1
2

Note

In the first sample making arrays [0, 4, 2] and [1, 2, 3] is impossible with k=3. After the modification, you can apply the operation with x=1 to the whole first array (its length is equal to k), and it will be equal to the second array.

In order to make arrays equal in the second sample before changes, you can apply operations with x=1 on subarray [1, 2] of a and with x=2 on subarray [2, 3] of b.

After all queries arrays will be equal [0, 3, 2] and [1, 0, 0]. The same operations make them equal [1, 2, 2].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tomya is a girl. She loves Chef Ciel very much.

Today, too, Tomya is going to Ciel's restaurant.
Of course, Tomya would like to go to Ciel's restaurant as soon as possible.
Therefore Tomya uses one of the shortest paths from Tomya's house to Ciel's restaurant.
On the other hand, Tomya is boring now to use the same path many times.
So Tomya wants to know the number of shortest paths from Tomya's house to Ciel's restaurant.
Your task is to calculate the number under the following assumptions.

This town has N intersections and M two way roads.
The i-th road connects from the Ai-th intersection to the Bi-th intersection, and its length is 

Ci.
Tomya's house is in the 1st intersection, and Ciel's restaurant is in the N-th intersection.

-----Input-----

The first line contains an integer T, the number of test cases.
Then T test cases follow.
The first line of each test case contains 2 integers N, M.
Then next M lines contains 3 integers denoting Ai, Bi and Ci.

-----Output-----

For each test case, print the number of shortest paths from Tomya's house to Ciel's restaurant.

-----Constraints-----

1 ≤ T ≤ 10

2 ≤ N ≤ 10

1 ≤ M ≤ N ∙ (N – 1) / 2

1 ≤ Ai, Bi ≤ N

1 ≤ Ci ≤ 10
Ai ≠ Bi

If i ≠ j and Ai = Aj, then Bi ≠ Bj

There is at least one path from Tomya's house to Ciel's restaurant.

-----Sample Input-----
2
3 3
1 2 3
2 3 6
1 3 7
3 3
1 2 3
2 3 6
1 3 9

-----Sample Output-----
1
2

-----Explanations-----

In the first sample, only one shortest path exists, which is 1-3.

In the second sample, both paths 1-2-3 and 1-3 are the shortest paths.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer n. Output its prime factorization.

If n = a1b1a2b2 ... akbk, where ak are prime numbers, the output of your program should look as follows: a1 a1 ... a1 a2 a2 ... a2 ... ak ak ... ak, where factors are ordered in non-decreasing order, and each factor ai is printed bi times.

Input

The only line of input contains an integer n (2 ≤ n ≤ 250).

Output

Output the prime factorization of n, as described above.

Examples

Input

245


Output

5 7 7 


Input

13


Output

13 

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Joe has been hurt on the Internet. Now he is storming around the house, destroying everything in his path.

Joe's house has *n* floors, each floor is a segment of *m* cells. Each cell either contains nothing (it is an empty cell), or has a brick or a concrete wall (always something one of three). It is believed that each floor is surrounded by a concrete wall on the left and on the right.

Now Joe is on the *n*-th floor and in the first cell, counting from left to right. At each moment of time, Joe has the direction of his gaze, to the right or to the left (always one direction of the two). Initially, Joe looks to the right.

Joe moves by a particular algorithm. Every second he makes one of the following actions: 
 -  If the cell directly under Joe is empty, then Joe falls down. That is, he moves to this cell, the gaze direction is preserved. -  Otherwise consider the next cell in the current direction of the gaze.   If the cell is empty, then Joe moves into it, the gaze direction is preserved. -  If this cell has bricks, then Joe breaks them with his forehead (the cell becomes empty), and changes the direction of his gaze to the opposite. -  If this cell has a concrete wall, then Joe just changes the direction of his gaze to the opposite (concrete can withstand any number of forehead hits). 
Joe calms down as soon as he reaches any cell of the first floor.

The figure below shows an example Joe's movements around the house.

Determine how many seconds Joe will need to calm down.

Input Specification:
The first line contains two integers *n* and *m* (2<=≤<=*n*<=≤<=100, 1<=≤<=*m*<=≤<=104).

Next *n* lines contain the description of Joe's house. The *i*-th of these lines contains the description of the (*n*<=-<=*i*<=+<=1)-th floor of the house — a line that consists of *m* characters: "." means an empty cell, "+" means bricks and "#" means a concrete wall.

It is guaranteed that the first cell of the *n*-th floor is empty.

Output Specification:
Print a single number — the number of seconds Joe needs to reach the first floor; or else, print word "Never" (without the quotes), if it can never happen.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Demo Input:
['3 5\n..+.#\n#+..+\n+.#+.\n', '4 10\n...+.##+.+\n+#++..+++#\n++.#++++..\n.+##.++#.+\n', '2 2\n..\n++\n']

Demo Output:
['14', '42\n', 'Never']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Duff is in love with lovely numbers! A positive integer x is called lovely if and only if there is no such positive integer a > 1 such that a^2 is a divisor of x. [Image] 

Malek has a number store! In his store, he has only divisors of positive integer n (and he has all of them). As a birthday present, Malek wants to give her a lovely number from his store. He wants this number to be as big as possible.

Malek always had issues in math, so he asked for your help. Please tell him what is the biggest lovely number in his store.


-----Input-----

The first and only line of input contains one integer, n (1 ≤ n ≤ 10^12).


-----Output-----

Print the answer in one line.


-----Examples-----
Input
10

Output
10

Input
12

Output
6



-----Note-----

In first sample case, there are numbers 1, 2, 5 and 10 in the shop. 10 isn't divisible by any perfect square, so 10 is lovely.

In second sample case, there are numbers 1, 2, 3, 4, 6 and 12 in the shop. 12 is divisible by 4 = 2^2, so 12 is not lovely, while 6 is indeed lovely.

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