vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Read a set of coordinates of three different points P1 (x1, y1), P2 (x2, y2), Q (xq, yq) on the plane, and line symmetry with point Q with the straight line passing through point P1 point P2 as the axis of symmetry. Create a program that outputs the point R (x, y) at the position of. Note that the point Q is not on its axis of symmetry.

<image>



input

The input consists of multiple datasets. Each dataset is given in the following format:


x1, y1, x2, y2, xq, yq


x1, y1, x2, y2, xq, yq (real numbers between -100 and 100) are given on one line separated by commas.

The number of datasets does not exceed 50.

output

Print x, y on a single line, separated by blanks, for each dataset. The output may contain an error of 0.0001 or less in real numbers.

Example

Input

1.0,0.0,-1.0,0.0,1.0,1.0
1.0,0.0,0.0,-1.0,3.0,0.0
0.0,1.0,0.0,-1.0,1.0,1.0


Output

1.000000 -1.000000
1.000000 2.000000
-1.000000 1.000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string of digits 0 – 9. The task is to count the number of substrings which when converting into integer form an even number.
Example 1:
Input : s = "1234".
Output : 6
Explanation: "2", "4", "12", "34", "234",
"1234" are 6 substring which are even.
Example 2:
Input : s = "154".
Output : 3
Explanation: "154", "54", "4" are the 
even substrings.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function evenNumSubstring() which takes the string as inputs and returns the count of even substring.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.

Example 1:


Input: 12
Output: 21


 

Example 2:


Input: 21
Output: -1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Are you fond of collecting some kind of stuff? Mike is crazy about collecting stamps. He is an active member of Stamp Collecting Сommunity(SCC). 

SCC consists of N members which are fond of philately. A few days ago Mike argued with the others from SCC. Mike told them that all stamps of the members could be divided in such a way that i'th member would get i postage stamps. Now Mike wants to know if he was right. The next SCC meeting is tomorrow. Mike still has no answer.

So, help Mike! There are N members in the SCC, i'th member has Ci stamps in his collection. Your task is to determine if it is possible to redistribute C1 + C2 + ... + Cn stamps among the members of SCC thus that i'th member would get i stamps.

-----Input-----
The first line contains one integer N, denoting the number of members of SCC.
The second line contains N integers Ci, denoting the numbers of the stamps in the collection of i'th member.

-----Output-----
The first line should contain YES, if we can obtain the required division, otherwise NO.

-----Constraints-----
1 ≤ N ≤ 100 000;
1 ≤  Ci ≤ 109.

-----Examples-----
Input:
5
7 4 1 1 2

Output:
YES

Input:
5
1 1 1 1 1

Output:
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two binary strings $S$ and $P$, each with length $N$. A binary string contains only characters '0' and '1'. For each valid $i$, let's denote the $i$-th character of $S$ by $S_i$.
You have to convert the string $S$ into $P$ using zero or more operations. In one operation, you should choose two indices $i$ and $j$ ($1 \leq i < j \leq N$) such that $S_i$ is '1' and $S_j$ is '0', and swap $S_i$ with $S_j$.
Determine if it is possible to convert $S$ into $P$ by performing some operations.

-----Input-----
- The first line of the input contains a single 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$.
- The second line contains a single string $S$.
- The third line contains a single string $P$.

-----Output-----
For each test case, print a single line containing the string "Yes" if it is possible to convert $S$ into $P$ or "No" otherwise (without quotes).

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq N \leq 10^5$
- $S$ and $P$ contain only characters '0' and '1'
- the sum of $N$ over all test cases does not exceed $10^5$

-----Subtasks-----
Subtask #1 (20 points):
- $N \leq 14$
- the sum of $N$ over all test cases does not exceed $100$
Subtask #2 (30 points): the sum of $N$ over all test cases does not exceed $1,000$
Subtask #3 (50 points): original constraints

-----Example Input-----
3
2
00
00
3
101
010
4
0110
0011

-----Example Output-----
Yes
No
Yes

-----Explanation-----
Example case 1: The strings are already equal.
Example case 2: It can be showed that it is impossible to convert $S$ into $P$.
Example case 3: You can swap $S_2$ with $S_4$. The strings will then be equal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two strings are anagrams of each other if the letters of one string can be rearranged to form the other string. Given a string, find the number of pairs of substrings of the string that are anagrams of each other.  

Example 

$s=mom$  

The list of all anagrammatic pairs is $[m,m],[mo,om]$ at positions $[[0],[2]],[[0,1],[1,2]]$ respectively.

Function Description

Complete the function sherlockAndAnagrams in the editor below.  

sherlockAndAnagrams has the following parameter(s):

string s: a string  

Returns  

int: the number of unordered anagrammatic pairs of substrings in $\boldsymbol{\mathrm{~S~}}$

Input Format

The first line contains an integer $\textit{q}$, the number of queries. 

Each of the next $\textit{q}$ lines contains a string $s$ to analyze. 

Constraints

$1\leq q\leq10$ 

$2\leq length of s\leq100$ 

$s$ contains only lowercase letters in the range ascii[a-z]. 

Sample Input 0
2
abba
abcd

Sample Output 0
4
0

Explanation 0

The list of all anagrammatic pairs is $[a,a],[ab,ba],[b,b]$ and $[abb,bba]$ at positions $[[0],[3]],[[0,1],[2,3]],[[1],[2]]$ and $[[0,1,2],[1,2,3]]$ respectively.  

No anagrammatic pairs exist in the second query as no character repeats.

Sample Input 1
2
ifailuhkqq
kkkk

Sample Output 1
3
10

Explanation 1

For the first query, we have anagram pairs $[i,i],[q,q]$ and $[if a,fai]$ at positions $[[0],[3]],[[8],[9]]$ and $[[0,1,2],[1,2,3]]$ respectively.

For the second query: 

There are 6 anagrams of the form $[k,k]$ at positions $[[0],[1]],[[0],[2]],[[0],[3]],[[1],[2]],[[1],[3]]$ and $[[2],[3]]$. 

There are 3 anagrams of the form $[kk,kk]$ at positions $[[0,1],[1,2]],[[0,1],[2,3]]$ and $[[1,2],[2,3]]$. 

There is 1 anagram of the form $[kkk,kkk]$ at position $[[0,1,2],[1,2,3]]$.

Sample Input 2
1
cdcd

Sample Output 2
5

Explanation 2

There are two anagrammatic pairs of length $1$: $[c,c]$ and $[d,d]$. 

There are three anagrammatic pairs of length $2$: $[cd,dc],[cd,cd],[dc,cd]$ at positions $[[0,1],[1,2]],[[0,1],[2,3]],[[1,2],[2,3]]$ respectively.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke got a present from his mother on his birthday. The present was a pair of two sequences a and b, consisting of positive integers. They satisfied all of the following properties:

* The sum of all elements of a is N.
* The sum of all elements of b is N.
* Any string of length N that satisfies the following two conditions (1) and (2) will also satisfy the condition (3).
* (1) Any of the following forms a palindrome: the first a_1 letters, the following a_2 letters, the following a_3 letters and so on.
* (2) Any of the following forms a palindrome: the first b_1 letters, the following b_2 letters, the following b_3 letters and so on.
* (3) All N letters are the same.



He was happy, until one day he lost both of the sequences. Now, he only remembers that the sequence a was a permutation of another sequence A of length M.

To bring him happiness again, his mother has decided to give him another pair of sequences a and b that satisfies his favorite properties and is consistent with his memory.

Constraints

* 1≦N≦10^5
* 1≦M≦100
* 1≦A_i≦10^5
* The sum of all A_i equals N.

Input

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


N M
A_1 A_2 ... A_M


Output

If there exists a pair of sequences a and b that satisfies the properties and is consistent with Snuke's memory, print three lines. The first line must contain the sequence a, the second line must contain the length of the sequence b, and the third line must contain the sequence b.

If such a pair does not exist (because Snuke's memory is wrong or some other reason), print a single line containing the word `Impossible` (case-sensitive).

Examples

Input

3 2
2 1


Output

1 2
1
3


Input

6 1
6


Output

6
3
1 2 3


Input

55 10
1 2 3 4 5 6 7 8 9 10


Output

Impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Taxis of Kharagpur are famous for making sharp turns. You are given the coordinates where a particular taxi was on a 2-D planes at N different moments: (x1, y1), (x2, y2), ..., (xN, yN). In between these coordinates, the taxi moves on a straight line. A turn at the i-th (2 ≤ i ≤ N-1) coordinate is said to be a sharp turn if the angle by which it turns at Point B = (xi, yi) when going from coordinates A = (xi-1, yi-1) to C = (xi+1, yi+1) via (xi, yi) is greater than 45 degrees. ie. suppose you extend the line segment AB further till a point D, then the angle DBC would be greater than 45 degrees.
You have to identify whether the taxi made a sharp turn somewhere or not (Please look at Output section for details). If it made a sharp turn, also identify whether it is possible to change the coordinates at one of the N moments to make sure that the taxi doesn't make any sharp turn. Note that all the N pairs of coordinates (including the new coordinates) should be integers and distinct and should have their x and y coordinates at least 0 and at most 50.

-----Input-----
- The first line of the input contains a single 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 number of moments at which you are given the information of the taxi's coordinates.
- Each of the next N lines contains two space-separated integers xi and yi denoting the x and y coordinates of the taxi at i-th moment.

-----Output-----
- For each test case, print a single line containing two space-separated strings, either of which can be a "yes" or "no" (without quotes). If there was no sharp turn, the first string should be "yes", and if there was a sharp turn, the first string should be "no". For the second string, you should tell whether it is possible to modify at most one coordinate in such a way that taxi doesn't make a sharp turn. Note that if the first string is "yes", then the second string would always be "yes".

-----Constraints-----
- 1 ≤ T ≤ 50
- 3 ≤ N ≤ 50
- 0 ≤ xi, yi ≤ 50
- It's guaranteed that all (xi, yi) pairs are distinct.

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

Output
yes yes
yes yes
no yes
no yes
no no

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

You can see that taxi is never making a sharp turn.

Example 3

You can see that taxi is making a sharp turn of 90 degrees, an angle greater than 45'. However, you can change the coordinates of the third points to (2, 1) to ensure that the angle remains <= 45'.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a permutation p of length n, find its subsequence s_1, s_2, …, s_k of length at least 2 such that:

  * |s_1-s_2|+|s_2-s_3|+…+|s_{k-1}-s_k| is as big as possible over all subsequences of p with length at least 2. 
  * Among all such subsequences, choose the one whose length, k, is as small as possible. 



If multiple subsequences satisfy these conditions, you are allowed to find any of them.

A sequence a is a subsequence of an array b if a can be obtained from b by deleting some (possibly, zero or all) elements.

A permutation of length n is an array of length n in which every element from 1 to n occurs exactly once.

Input

The first line contains an integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer n (2 ≤ n ≤ 10^5) — the length of the permutation p.

The second line of each test case contains n integers p_1, p_2, …, p_{n} (1 ≤ p_i ≤ n, p_i are distinct) — the elements of the permutation p.

The sum of n across the test cases doesn't exceed 10^5.

Output

For each test case, the first line should contain the length of the found subsequence, k. The second line should contain s_1, s_2, …, s_k — its elements.

If multiple subsequences satisfy these conditions, you are allowed to find any of them.

Example

Input


2
3
3 2 1
4
1 3 4 2


Output


2
3 1 
3
1 4 2 

Note

In the first test case, there are 4 subsequences of length at least 2:

  * [3,2] which gives us |3-2|=1. 
  * [3,1] which gives us |3-1|=2. 
  * [2,1] which gives us |2-1|=1. 
  * [3,2,1] which gives us |3-2|+|2-1|=2. 



So the answer is either [3,1] or [3,2,1]. Since we want the subsequence to be as short as possible, the answer is [3,1].

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Inzane finally found Zane with a lot of money to spare, so they together decided to establish a country of their own.

Ruling a country is not an easy job. Thieves and terrorists are always ready to ruin the country's peace. To fight back, Zane and Inzane have enacted a very effective law: from each city it must be possible to reach a police station by traveling at most *d* kilometers along the roads.

There are *n* cities in the country, numbered from 1 to *n*, connected only by exactly *n*<=-<=1 roads. All roads are 1 kilometer long. It is initially possible to travel from a city to any other city using these roads. The country also has *k* police stations located in some cities. In particular, the city's structure satisfies the requirement enforced by the previously mentioned law. Also note that there can be multiple police stations in one city.

However, Zane feels like having as many as *n*<=-<=1 roads is unnecessary. The country is having financial issues, so it wants to minimize the road maintenance cost by shutting down as many roads as possible.

Help Zane find the maximum number of roads that can be shut down without breaking the law. Also, help him determine such roads.

Input Specification:
The first line contains three integers *n*, *k*, and *d* (2<=≤<=*n*<=≤<=3·105, 1<=≤<=*k*<=≤<=3·105, 0<=≤<=*d*<=≤<=*n*<=-<=1) — the number of cities, the number of police stations, and the distance limitation in kilometers, respectively.

The second line contains *k* integers *p*1,<=*p*2,<=...,<=*p**k* (1<=≤<=*p**i*<=≤<=*n*) — each denoting the city each police station is located in.

The *i*-th of the following *n*<=-<=1 lines contains two integers *u**i* and *v**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*, *u**i*<=≠<=*v**i*) — the cities directly connected by the road with index *i*.

It is guaranteed that it is possible to travel from one city to any other city using only the roads. Also, it is possible from any city to reach a police station within *d* kilometers.

Output Specification:
In the first line, print one integer *s* that denotes the maximum number of roads that can be shut down.

In the second line, print *s* distinct integers, the indices of such roads, in any order.

If there are multiple answers, print any of them.

Demo Input:
['6 2 4\n1 6\n1 2\n2 3\n3 4\n4 5\n5 6\n', '6 3 2\n1 5 6\n1 2\n1 3\n1 4\n1 5\n5 6\n']

Demo Output:
['1\n5\n', '2\n4 5 ']

Note:
In the first sample, if you shut down road 5, all cities can still reach a police station within *k* = 4 kilometers.

In the second sample, although this is the only largest valid set of roads that can be shut down, you can print either 4 5 or 5 4 in the second line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to implement the function strstr. The function takes two strings as arguments (s,x) and  locates the occurrence of the string x in the string s. The function returns and integer denoting the first occurrence of the string x in s (0 based indexing).
Note: You are not allowed to use inbuilt function.
 
Example 1:
Input:
s = GeeksForGeeks, x = Fr
Output: -1
Explanation: Fr is not present in the
string GeeksForGeeks as substring.
 
Example 2:
Input:
s = GeeksForGeeks, x = For
Output: 5
Explanation: For is present as substring
in GeeksForGeeks from index 5 (0 based
indexing).
 
Your Task:
You don't have to take any input. Just complete the strstr() function which takes two strings str, target as an input parameter. The function returns -1 if no match if found else it returns an integer denoting the first occurrence of the x in the string s.
 
Expected Time Complexity: O(|s|*|x|)
Expected Auxiliary Space: O(1)
Note : Try to solve the question in constant space complexity.
 
Constraints:
1 <= |s|,|x| <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke loves colorful balls. He has a total of N×K balls, K in each of his favorite N colors. The colors are numbered 1 through N.

He will arrange all of the balls in a row from left to right, in arbitrary order. Then, for each of the N colors, he will paint the leftmost ball of that color into color 0, a color different from any of the N original colors.

After painting, how many sequences of the colors of the balls are possible? Find this number modulo 10^9+7.

Constraints

* 1≤N,K≤2,000

Input

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


N K


Output

Print the number of the possible sequences of the colors of the balls after painting, modulo 10^9+7.

Examples

Input

2 2


Output

4


Input

3 1


Output

1


Input

2 3


Output

14


Input

2000 2000


Output

546381702

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a list intervals of n intervals, the ith element [s, e, p] denotes the starting point s, ending point e, and the profit p earned by choosing the ith interval. Find the maximum profit one can achieve by choosing a subset of non-overlapping intervals.
Two intervals [s1, e1, p1] and [s2, e2, p2] are said to be non-overlapping if [e1 <= s2] and [s1 < s2].
Example 1:
Input:
n = 3
intervals = {
{1, 2, 4},
{1, 5, 7},
{2, 4, 4}
}
Output:
8
Explanation:
One can choose intervals [1, 2, 4] and [2, 4, 4] for a 
profit of 8.
Example 2:
Input:
n = 3
intervals = {
{1, 4, 4},
{2, 3, 7},
{2, 3, 4}
}
Output:
7
Explanation:
One can choose interval [2, 3, 7] for a profit of 7.
Your Task:
You don't need to print or output anything. Complete the function maximum_profit() which takes an integer n and a 2D integer array intervals and returns an integer, denoting the maximum profit which one can get by choosing the non-overlapping intervals.
Constraints:
	1 <= n and n <= 10^{4}
	1 <= starting point of ith interval < ending point of ith interval <= 10^{5}
	1 <= profit earned by choosing ith interval <= 10^{5}

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

 Replace the pair of exclamation marks and question marks to spaces(from the left to the right). A pair of exclamation marks and question marks must has the same number of "!" and "?". 
 
 That is: "!" and "?" is a pair; "!!" and "??" is a pair; "!!!" and "???" is a pair; and so on..

# Examples

```
replace("!!") === "!!"
replace("!??") === "!??"
replace("!?") === "  "
replace("!!??") === "    "
replace("!!!????") === "!!!????"
replace("!??!!") === "!    "
replace("!????!!!?") === " ????!!! " 
replace("!?!!??!!!?") === "      !!!?"
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're looking through different hex codes, and having trouble telling the difference between  #000001  and  #100000 

We need a way to tell which is red, and which is blue!

That's where you create ```hex_color()```!

It should read an RGB input, and return whichever value (red, blue, or green) is of greatest concentration!

But, if multiple colors are of equal concentration, you should return their mix!

```python
red + blue = magenta

green + red = yellow

blue + green = cyan

red + blue + green = white
```

One last thing, if the string given is empty, or has all 0's, return black!

Examples:
```python
hex_color('087 255 054') == 'green'
hex_color('181 181 170') == 'yellow'
hex_color('000 000 000') == 'black'
hex_color('001 001 001') == 'white'
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This problem consists of two subproblems: for solving subproblem E1 you will receive 11 points, and for solving subproblem E2 you will receive 13 points.

A tree is an undirected connected graph containing no cycles. The distance between two nodes in an unweighted tree is the minimum number of edges that have to be traversed to get from one node to another.

You are given 3 trees that have to be united into a single tree by adding two edges between these trees. Each of these edges can connect any pair of nodes from two trees. After the trees are connected, the distances between all unordered pairs of nodes in the united tree should be computed. What is the maximum possible value of the sum of these distances?

Input

The first line contains three space-separated integers n1, n2, n3 — the number of vertices in the first, second, and third trees, respectively. The following n1 - 1 lines describe the first tree. Each of these lines describes an edge in the first tree and contains a pair of integers separated by a single space — the numeric labels of vertices connected by the edge. The following n2 - 1 lines describe the second tree in the same fashion, and the n3 - 1 lines after that similarly describe the third tree. The vertices in each tree are numbered with consecutive integers starting with 1.

The problem consists of two subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.

  * In subproblem E1 (11 points), the number of vertices in each tree will be between 1 and 1000, inclusive. 
  * In subproblem E2 (13 points), the number of vertices in each tree will be between 1 and 100000, inclusive. 

Output

Print a single integer number — the maximum possible sum of distances between all pairs of nodes in the united tree.

Examples

Input

2 2 3
1 2
1 2
1 2
2 3


Output

56


Input

5 1 4
1 2
2 5
3 4
4 2
1 2
1 3
1 4


Output

151

Note

Consider the first test case. There are two trees composed of two nodes, and one tree with three nodes. The maximum possible answer is obtained if the trees are connected in a single chain of 7 vertices.

In the second test case, a possible choice of new edges to obtain the maximum answer is the following: 

  * Connect node 3 from the first tree to node 1 from the second tree; 
  * Connect node 2 from the third tree to node 1 from the second tree.

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