vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given two arrays a and b, each consisting of n positive integers, and an integer x. Please determine if one can rearrange the elements of b so that a_i + b_i ≤ x holds for each i (1 ≤ i ≤ n).

Input

The first line of input contains one integer t (1 ≤ t ≤ 100) — the number of test cases. t blocks follow, each describing an individual test case.

The first line of each test case contains two integers n and x (1 ≤ n ≤ 50; 1 ≤ x ≤ 1000) — the length of arrays a and b, and the parameter x, described in the problem statement.

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_1 ≤ a_2 ≤ ... ≤ a_n ≤ x) — the elements of array a in non-descending order.

The third line of each test case contains n integers b_1, b_2, …, b_n (1 ≤ b_1 ≤ b_2 ≤ ... ≤ b_n ≤ x) — the elements of array b in non-descending order.

Test cases are separated by a blank line.

Output

For each test case print Yes if one can rearrange the corresponding array b so that a_i + b_i ≤ x holds for each i (1 ≤ i ≤ n) or No otherwise.

Each character can be printed in any case.

Example

Input


4
3 4
1 2 3
1 1 2

2 6
1 4
2 5

4 4
1 2 3 4
1 2 3 4

1 5
5
5


Output


Yes
Yes
No
No

Note

In the first test case, one can rearrange b so it'll look like [1, 2, 1]. In this case, 1 + 1 ≤ 4; 2 + 2 ≤ 4; 3 + 1 ≤ 4.

In the second test case, one can set b to [5, 2], then 1 + 5 ≤ 6; 4 + 2 ≤ 6.

In the third test case, no matter how one shuffles array b, a_4 + b_4 = 4 + b_4 > 4.

In the fourth test case, there is only one rearrangement of array b and it doesn't satisfy the condition since 5 + 5 > 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko has received a homework assignment to compute the greatest common divisor of the two positive integers $A$ and $B$. Since the numbers are quite large, the teacher provided him with $N$ smaller integers whose product is $A$, and $M$ integers with product $B$.

Mirko would like to verify his result, so he has asked you to write a program to solve his problem. If the result is more than $9$ digits long, output only the last $9$ digits.

-----Input-----
The first line of input contains the positive integer $N$ ($1 \le N \le 1000$).

The second line of input contains $N$ space-separated positive integers less than $1000000000$, whose product is the number $A$.

The third line of input contains the positive integer $M$ ($1 \le M \le 1000$).

The fourth line of input contains $M$ space-separated positive integers less than $1000000000$, whose product is the number $B$.

-----Output-----
The first and only line of output must contain the greatest common divisor of numbers $A$ and $B$. If the result is more than $9$ digits long, output only the last (least significant) $9$ digits.

-----Examples-----
Sample Input 1:
3
2 3 5
2
4 5
Sample Output 1:
10

Sample Input 2:
4
6 2 3 4
1
1
Sample Output 2:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ computers in a row, all originally off, and Phoenix wants to turn all of them on. He will manually turn on computers one at a time. At any point, if computer $i-1$ and computer $i+1$ are both on, computer $i$ $(2 \le i \le n-1)$ will turn on automatically if it is not already on. Note that Phoenix cannot manually turn on a computer that already turned on automatically.

If we only consider the sequence of computers that Phoenix turns on manually, how many ways can he turn on all the computers? Two sequences are distinct if either the set of computers turned on manually is distinct, or the order of computers turned on manually is distinct. Since this number may be large, please print it modulo $M$.


-----Input-----

The first line contains two integers $n$ and $M$ ($3 \le n \le 400$; $10^8 \le M \le 10^9$) — the number of computers and the modulo. It is guaranteed that $M$ is prime.


-----Output-----

Print one integer — the number of ways to turn on the computers modulo $M$.


-----Examples-----

Input
3 100000007
Output
6
Input
4 100000007
Output
20
Input
400 234567899
Output
20914007


-----Note-----

In the first example, these are the $6$ orders in which Phoenix can turn on all computers:

$[1,3]$. Turn on computer $1$, then $3$. Note that computer $2$ turns on automatically after computer $3$ is turned on manually, but we only consider the sequence of computers that are turned on manually.

$[3,1]$. Turn on computer $3$, then $1$.

$[1,2,3]$. Turn on computer $1$, $2$, then $3$.

$[2,1,3]$

$[2,3,1]$

$[3,2,1]$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two arrays `arr1` and `arr2`, where `arr2` always contains integers.

Write the function `find_array(arr1, arr2)` such that:

For `arr1 = ['a', 'a', 'a', 'a', 'a']`, `arr2 = [2, 4]`
`find_array returns ['a', 'a']`

For `arr1 = [0, 1, 5, 2, 1, 8, 9, 1, 5]`, `arr2 = [1, 4, 7]`
`find_array returns [1, 1, 1]`

For `arr1 = [0, 3, 4]`, `arr2 = [2, 6]`
`find_array returns [4]`

For `arr1=["a","b","c","d"]` , `arr2=[2,2,2]`,
`find_array returns ["c","c","c"]`

For `arr1=["a","b","c","d"]`, `arr2=[3,0,2]`
`find_array returns ["d","a","c"]`

If either `arr1` or `arr2` is empty, you should return an empty arr (empty list in python,
empty vector in c++). Note for c++ use std::vector arr1, arr2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two fractions a/b and c/d, compare them and print the larger of the two.
Example 1:
Input:
s = "5/6, 11/45"
Output: 5/6
Explanation:
5/6=0.8333... and 11/45=0.2444.... 
Clearly, 5/6 is greater, so we output it.
 
Example 2:
Input:
s = "8/1, 8/1"
Output: equal
Explanation:
We can see that both the fractions are same, 
so they are equal.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function compareFrac() which takes the string s as input parameters and returns the fraction that is greater. If they are equal, then return "equal".
Expected Time Complexity: O(len|s|)
Expected Auxiliary Space: O(1)
 
Constraints:
0<=a,c<=1000
1<=b,d<=1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the largest basin size in a given matrix.               
       9 9 9 8 8 8     
       8 8 8 7 7 7       
       7 7 7 7 7 7 
       8 8 8 8 9 9         
       5 5 5 5 6 3       
       5 5 5 3 3 3       
For the above example, the Bold values form the maximum size basin. Answer for above case is: 9

INPUT
First line of the input contains N( Number of rows ) and M( Number of columns) separated by a space. 
The next N lines contain M space separated elements representing the array. See sample input output for more clarity 

OUTPUT
Print the size of the maximum size basin.

SAMPLE INPUT
6 6
9 9 9 8 8 8
8 8 8 7 7 7
7 7 7 7 7 7
8 8 8 8 9 9
5 5 5 5 6 3
5 5 5 3 3 3

SAMPLE OUTPUT
9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array $A_1, A_2, ..., A_N$, count the number of subarrays of array $A$ which are non-decreasing.

A subarray $A[i, j]$, where $1 ≤ i ≤ j ≤ N$ is a sequence of integers $A_i, A_i+1, ..., A_j$.
A subarray $A[i, j]$ is non-decreasing if $A_i ≤ A_i+1 ≤ A_i+2 ≤ ... ≤ A_j$. You have to count the total number of such subarrays.

-----Input-----
- 
The first line of input contains an integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- 
The first line of each test case contains a single integer $N$ denoting the size of array.
- 
The second line contains $N$ space-separated integers $A_1$, $A_2$, …, $A_N$ denoting the elements of the array.

-----Output-----
For each test case, output in a single line the required answer.

-----Constraints-----
- $1 ≤ T ≤ 5$
- $1 ≤ N ≤ 10^5$
- $1 ≤ A_i ≤ 10^9$

-----Subtasks-----
- Subtask 1 (20 points) : $1 ≤ N ≤ 100$
- Subtask 2 (30 points) : $1 ≤ N ≤ 1000$
- Subtask 3 (50 points) : Original constraints

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

-----Sample Output:-----
6
1

-----Explanation-----
Example case 1.

All valid subarrays are $A[1, 1], A[1, 2], A[2, 2], A[3, 3], A[3, 4], A[4, 4]$.

Note that singleton subarrays are identically non-decreasing.
Example case 2.

Only single subarray $A[1, 1]$ is non-decreasing.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya is an active Internet user. One day he came across an Internet resource he liked, so he wrote its address in the notebook. We know that the address of the written resource has format:

<protocol>://<domain>.ru[/<context>]

where:

  * <protocol> can equal either "http" (without the quotes) or "ftp" (without the quotes), 
  * <domain> is a non-empty string, consisting of lowercase English letters, 
  * the /<context> part may not be present. If it is present, then <context> is a non-empty string, consisting of lowercase English letters. 



If string <context> isn't present in the address, then the additional character "/" isn't written. Thus, the address has either two characters "/" (the ones that go before the domain), or three (an extra one in front of the context).

When the boy came home, he found out that the address he wrote in his notebook had no punctuation marks. Vasya must have been in a lot of hurry and didn't write characters ":", "/", ".".

Help Vasya to restore the possible address of the recorded Internet resource.

Input

The first line contains a non-empty string that Vasya wrote out in his notebook. This line consists of lowercase English letters only. 

It is guaranteed that the given string contains at most 50 letters. It is guaranteed that the given string can be obtained from some correct Internet resource address, described above.

Output

Print a single line — the address of the Internet resource that Vasya liked. If there are several addresses that meet the problem limitations, you are allowed to print any of them.

Examples

Input

httpsunrux


Output

http://sun.ru/x


Input

ftphttprururu


Output

ftp://http.ru/ruru

Note

In the second sample there are two more possible answers: "ftp://httpruru.ru" and "ftp://httpru.ru/ru".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Misha hacked the Codeforces site. Then he decided to let all the users change their handles. A user can now change his handle any number of times. But each new handle must not be equal to any handle that is already used or that was used at some point.

Misha has a list of handle change requests. After completing the requests he wants to understand the relation between the original and the new handles of the users. Help him to do that.


-----Input-----

The first line contains integer q (1 ≤ q ≤ 1000), the number of handle change requests.

Next q lines contain the descriptions of the requests, one per line.

Each query consists of two non-empty strings old and new, separated by a space. The strings consist of lowercase and uppercase Latin letters and digits. Strings old and new are distinct. The lengths of the strings do not exceed 20.

The requests are given chronologically. In other words, by the moment of a query there is a single person with handle old, and handle new is not used and has not been used by anyone.


-----Output-----

In the first line output the integer n — the number of users that changed their handles at least once.

In the next n lines print the mapping between the old and the new handles of the users. Each of them must contain two strings, old and new, separated by a space, meaning that before the user had handle old, and after all the requests are completed, his handle is new. You may output lines in any order.

Each user who changes the handle must occur exactly once in this description.


-----Examples-----
Input
5
Misha ILoveCodeforces
Vasya Petrov
Petrov VasyaPetrov123
ILoveCodeforces MikeMirzayanov
Petya Ivanov

Output
3
Petya Ivanov
Misha MikeMirzayanov
Vasya VasyaPetrov123

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Monocarp plays "Rage of Empires II: Definitive Edition" — a strategic computer game. Right now he's planning to attack his opponent in the game, but Monocarp's forces cannot enter the opponent's territory since the opponent has built a wall.

The wall consists of $n$ sections, aligned in a row. The $i$-th section initially has durability $a_i$. If durability of some section becomes $0$ or less, this section is considered broken.

To attack the opponent, Monocarp needs to break at least two sections of the wall (any two sections: possibly adjacent, possibly not). To do this, he plans to use an onager — a special siege weapon. The onager can be used to shoot any section of the wall; the shot deals $2$ damage to the target section and $1$ damage to adjacent sections. In other words, if the onager shoots at the section $x$, then the durability of the section $x$ decreases by $2$, and the durability of the sections $x - 1$ and $x + 1$ (if they exist) decreases by $1$ each.

Monocarp can shoot at any sections any number of times, he can even shoot at broken sections.

Monocarp wants to calculate the minimum number of onager shots needed to break at least two sections. Help him!


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of sections.

The second line contains the sequence of integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$), where $a_i$ is the initial durability of the $i$-th section.


-----Output-----

Print one integer — the minimum number of onager shots needed to break at least two sections of the wall.


-----Examples-----

Input
5
20 10 30 10 20
Output
10
Input
3
1 8 1
Output
1
Input
6
7 6 6 8 5 8
Output
4
Input
6
14 3 8 10 15 4
Output
4
Input
4
1 100 100 1
Output
2
Input
3
40 10 10
Output
7


-----Note-----

In the first example, it is possible to break the $2$-nd and the $4$-th section in $10$ shots, for example, by shooting the third section $10$ times. After that, the durabilities become $[20, 0, 10, 0, 20]$. Another way of doing it is firing $5$ shots at the $2$-nd section, and another $5$ shots at the $4$-th section. After that, the durabilities become $[15, 0, 20, 0, 15]$.

In the second example, it is enough to shoot the $2$-nd section once. Then the $1$-st and the $3$-rd section will be broken.

In the third example, it is enough to shoot the $2$-nd section twice (then the durabilities become $[5, 2, 4, 8, 5, 8]$), and then shoot the $3$-rd section twice (then the durabilities become $[5, 0, 0, 6, 5, 8]$). So, four shots are enough to break the $2$-nd and the $3$-rd section.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of integers. Calculate the sum of its elements.

Input

The i-th line of the input contains an integer ai (0 ≤ a ≤ 1000) — the i-th element of the array. The size of the array is between 1 and 10, inclusive. Note that the size of the array is not given explicitly!

Output

Output a single integer — the sum of the elements of the array.

Examples

Input

2
15
110
3


Output

130


Input

90
0
21
331
45


Output

487

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pentagonal numbers are figurate numbers which can be calculated using the formula pn = (3n2 - n) / 2 (always integer). You are given n; calculate n-th pentagonal number.

Input

The only line of input contains an integer n (1 ≤ n ≤ 100).

Output

Output the n-th pentagonal number.

Examples

Input

2


Output

5


Input

5


Output

35

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Manasa is a student in the department of Mathematics. She is pretty good at doing calculations involving small numbers, but large numbers scare her. So she wants you to help her in the following calculations.

Given two numbers in the following manner:

$A=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times\text{...}\times p_N^{a_N}$
$B=p_1^{b_1}\times p_2^{b_2}\times p_3^{b_3}\times\text{...}\times p_N^{b_N}$

($p_i$ is a prime number, and all the $p_i$'s are distinct)

She wants you to calculate ${S}$ for her, where ${S}$ is the sum of $m+n$ for all pairs of numbers  where $m\leq n$, $\text{gcd}(m,n)=B$ and $\text{lcm}(m,n)=A$. In other words:

$S=\sum_{\begin{equation}\begin{aligned}gcd(m,n)=B\\ \text{lcm}(m,n)=A\\ m\leq n}}(m+n)$ 

As the value of ${S}$ can be very large, she wants you to print $S\:\text{mod}\:10^9+7$.

Input Format 

The first line contains an integer $N$, the number of prime factors. 

Each of the next $N$ lines contains three numbers: $p_i$, $b_i$ and $a_i$.

Output Format 

Print the value of $S\:\text{mod}\:10^9+7$.

Constraints  

$1\leq N\leq500$ 

$2\leq p_i\leq5000$ 

$1\leq a_i\leq10^9$ 

$1\leq b_i\leq10^9$ 

$b_i\leq a_i$  

Sample Input

2
2 1 2 
3 1 2

Sample Output

72

Explanation

We have $B=6$ and $A=36$. There are two pairs of integers $(m,n)$ with ${gcd}$ equal to ${6}$ and ${lcm}$ equal to $36$, and such that $m\leq n$. These are $(12,18)$ and $(6,36)$:

$\text{gcd}(12,18)=6$ and $\text{lcm}(12,18)=36$  
$\text{gcd}(6,36)=6$ and $\text{lcm}(6,36)=36$  

Hence, $S=(12+18)+(6+36)=72$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given four integers: H, W, h and w (1 ≤ h ≤ H, 1 ≤ w ≤ W). Determine whether there exists a matrix such that all of the following conditions are held, and construct one such matrix if the answer is positive:

* The matrix has H rows and W columns.
* Each element of the matrix is an integer between -10^9 and 10^9 (inclusive).
* The sum of all the elements of the matrix is positive.
* The sum of all the elements within every subrectangle with h rows and w columns in the matrix is negative.

Constraints

* 1 ≤ h ≤ H ≤ 500
* 1 ≤ w ≤ W ≤ 500

Input

Input is given from Standard Input in the following format:


H W h w


Output

If there does not exist a matrix that satisfies all of the conditions, print `No`.

Otherwise, print `Yes` in the first line, and print a matrix in the subsequent lines in the following format:


a_{11} ... a_{1W}
:
a_{H1} ... a_{HW}


Here, a_{ij} represents the (i,\ j) element of the matrix.

Examples

Input

3 3 2 2


Output

Yes
1 1 1
1 -4 1
1 1 1


Input

2 4 1 2


Output

No


Input

3 4 2 3


Output

Yes
2 -5 8 7
3 -5 -4 -5
2 1 -1 7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has an array A of length N.

Let f(i) denote the sum A_{1} + A_{2} + \dots + A_{i} \, and let g(i) denote the sum A_{i} + A_{i + 1} + \dots + A_{N}. 

Chef creates another array B of length N such that B_{i} = f(i) + g(i) for all 1 ≤ i ≤ N.

Now, Chef has lost the original array A and needs your help to recover it, given array B. It is guaranteed that Chef has obtained the array B from a valid array A.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the array A.
- The second line of each test case contains N space-separated integers B_{1}, B_{2}, \dots, B_{N} denoting the array B.

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

For each testcase, output N space separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A. 

Note that 1 ≤ A_{i} ≤ 10^{5} must hold for all 1 ≤ i ≤ N and it is guaranteed that a valid array A that meets these constraints exists.

If there are multiple answers, output any.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ B_{i} ≤ 2 \cdot 10^{10}$
- Th sum of $N$ over all test cases does not exceed $10^{5}$.
$1 ≤ A_{i} ≤ 10^{5}$
- It is guaranteed that a valid array $A$ always exists.

----- Sample Input 1 ------ 
4
1
6
3
7 8 9
4
13 15 13 14
2
25 20

----- Sample Output 1 ------ 
3 
1 2 3 
2 4 2 3 
10 5 

----- explanation 1 ------ 
Test case 1: For $A = [3]$, $B = [6]$. $B_{1} = f(1) + g(1) = 3 + 3 = 6$.

Test case 2: For $A = [1, 2, 3]$, $B = [7, 8, 9]$.
- $B_{1} = f(1) + g(1) = \underline{1} + \underline{1 + 2 + 3} = 7$
- $B_{2} = f(2) + g(2) = \underline{1 + 2} + \underline{2 + 3} = 8$
- $B_{3} = f(3) + g(3) = \underline{1 + 2 + 3} + \underline{3} = 9$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jeff's friends know full well that the boy likes to get sequences and arrays for his birthday. Thus, Jeff got sequence p_1, p_2, ..., p_{n} for his birthday.

Jeff hates inversions in sequences. An inversion in sequence a_1, a_2, ..., a_{n} is a pair of indexes i, j (1 ≤ i < j ≤ n), such that an inequality a_{i} > a_{j} holds.

Jeff can multiply some numbers of the sequence p by -1. At that, he wants the number of inversions in the sequence to be minimum. Help Jeff and find the minimum number of inversions he manages to get.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 2000). The next line contains n integers — sequence p_1, p_2, ..., p_{n} (|p_{i}| ≤ 10^5). The numbers are separated by spaces.


-----Output-----

In a single line print the answer to the problem — the minimum number of inversions Jeff can get.


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

Output
0

Input
9
-2 0 -1 0 -1 2 1 0 -1

Output
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S, find the longest palindromic substring in S. Substring of string S: S[ i . . . . j ] where 0 ≤ i ≤ j < len(S). Palindrome string: A string that reads the same backward. More formally, S is a palindrome if reverse(S) = S. In case of conflict, return the substring which occurs first ( with the least starting index).
Example 1:
Input:
S = "aaaabbaa"
Output: aabbaa
Explanation: The longest Palindromic
substring is "aabbaa".
Example 2:
Input: 
S = "abc"
Output: a
Explanation: "a", "b" and "c" are the 
longest palindromes with same length.
The result is the one with the least
starting index.
Your Task:
You don't need to read input or print anything. Your task is to complete the function longestPalin() which takes the string S as input and returns the longest palindromic substring of S.
Expected Time Complexity: O(|S|^{2}).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ |S| ≤ 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You want to repaint your house entirely for an upcoming occasion. The total area of your house is D units. There are a total of N workers. The i^th worker has his available time Ti, hiring cost Xi and speed Yi. This means that he is available for hiring from time Ti  and remains available ever since. Once available, you can hire him with cost Xi, after which he will start painting the house immediately, covering exactly Yi units of house with paint per time unit. You may or may not hire a worker and can also hire or fire him at any later point of time. However, no more than 1 worker can be painting the house at a given time.

Since you want the work to be done as fast as possible, figure out a way to hire the workers, such that your house gets painted at the earliest possible time, with minimum cost to spend for hiring workers.

Note: You can hire a previously hired worker without paying him again.

INPUT

The first line of input contains two integers "N D", the number of workers and the area of your house respectively. The i^th of the next N lines denotes the i^th worker, and contains three integers "Ti Xi Yi", described in the statement.

OUTPUT

Output one integer, the minimum cost that you can spend in order to get your house painted at the earliest.

CONSTRAINTS

1 ≤ N, T, X, Y ≤ 10^5
1 ≤ D ≤ 10^11

SAMPLE INPUT
3 3
1 1 1
2 2 2
3 1 5

SAMPLE OUTPUT
3

Explanation

We can hire the first worker at cost of 1 and second at cost of 2, to finish painting at the minimum time of exactly 2 time units.

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