vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Mike decided to teach programming to children in an elementary school. He knows that it is not an easy task to interest children in that age to code. That is why he decided to give each child two sweets.

Mike has $n$ sweets with sizes $a_1, a_2, \ldots, a_n$. All his sweets have different sizes. That is, there is no such pair $(i, j)$ ($1 \leq i, j \leq n$) such that $i \ne j$ and $a_i = a_j$.

Since Mike has taught for many years, he knows that if he gives two sweets with sizes $a_i$ and $a_j$ to one child and $a_k$ and $a_p$ to another, where $(a_i + a_j) \neq (a_k + a_p)$, then a child who has a smaller sum of sizes will be upset. That is, if there are two children who have different sums of sweets, then one of them will be upset. Apparently, Mike does not want somebody to be upset. 

Mike wants to invite children giving each of them two sweets. Obviously, he can't give one sweet to two or more children. His goal is to invite as many children as he can. 

Since Mike is busy preparing to his first lecture in the elementary school, he is asking you to find the maximum number of children he can invite giving each of them two sweets in such way that nobody will be upset.


-----Input-----

The first line contains one integer $n$ ($2 \leq n \leq 1\,000$) — the number of sweets Mike has.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^5$) — the sizes of the sweets. It is guaranteed that all integers are distinct.


-----Output-----

Print one integer — the maximum number of children Mike can invite giving each of them two sweets in such way that nobody will be upset.


-----Examples-----
Input
8
1 8 3 11 4 9 2 7

Output
3

Input
7
3 1 7 11 9 2 12

Output
2



-----Note-----

In the first example, Mike can give $9+2=11$ to one child, $8+3=11$ to another one, and $7+4=11$ to the third child. Therefore, Mike can invite three children. Note that it is not the only solution.

In the second example, Mike can give $3+9=12$ to one child and $1+11$ to another one. Therefore, Mike can invite two children. Note that it is not the only solution.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Instead of worrying about the current hyperinflation you decide to go down to the local bar and have a drink.

The prices at the bar are displayed using magnetic signs with numbers printed on them, with each magnet showing one or more digits. For instance, the price of $1106$ megacredits is displayed like this:


While the bartender is busy serving the next customer, you have just enough time to rearrange the price of your favourite beverage to make it as cheap as possible. But be quick about it!

Invidual magnets can be moved around in any order and turned upside-down. The numbers are shown in a script that makes it difficult for the bartender to distinguish $0$, $1$, and $8$ from their upside-down counterpart. Moreover, $6$ and $9$ look the same when one is turned upside-down. The example price above could be made almost ten times cheaper by turning the first magnet:


You have to use all the magnets, otherwise the bartender will immediately suspect foul play.

-----Input-----
On the first line, the number $n$ of magnets, with $1\in \{ 1,\ldots , 1000\} $. On each of the following $n$ lines, exactly one sequence $m_ i$ of digits describing the $i$th magnet. Each magnet $m_ i$ for $i\in \{ 1,\ldots , n\} $ consists of at least one and at most $10$ digits from $0$, $1$, $\ldots $, $9$. The price currently displayed on the bar is the integer described by the juxtaposition $m_1\cdots m_ n$ of the magnets in the order they are given, from left to right. Note that a magnet can be all $0$s, even though the current price at the bar, alas!, is certainly not.

-----Output-----
A single line containing the cheapest price formed by the magnets $m_1,\ldots ,m_ n$, rearranged in any order, and each of them possibly turned upside-down.

-----Examples-----
Sample Input:
2
110
6
Sample Output:
0116

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This time your assignment is really simple.

Calculate GCD(1, 1) * GCD(1, 2) * ... * GCD(1, M) * GCD(2, 1) * GCD(2, 2) * ... * GCD(2, M) * ... * GCD(N, 1) * GCD(N, 2) * ... * GCD(N, M).

where GCD is defined as the Greatest Common Divisor. 

Input Format

The first and only line contains two space separated integers N and M.

Output Format

Output the required product modulo 10^{9}+7.

Constraints

1 <= N, M <= 1.5 * 10^{7}

Sample input:

4 4

Sample output:

96

Explanation

For the above testcase, N = 4, M = 4. So, 

GCD(1, 1) * GCD(1, 2) * ...... * GCD(4, 4) = 1 * 1 * 1 * 1 * 1 * 2 * 1 * 2 * 1 * 1 * 3 * 1 * 1 * 2 * 1 * 4 = 96.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chandan is back with his array to blow your mind. As usual Chandan has an array consisting of N integers .He allows you to perform 2 kinds of operation on his array.

Type 1 : Increment any integer of the array by 1.

Type 2 : Decrement any integer of the array by 1.

You can perform these operation as many times as you want on his array.

Each  operation of Type 1 costs 3 while each operation of Type 2 costs 5.

Now Chandan wants to have K equal elements in his array.So he asks you to tell him the minimum cost required in obtaining K equal elements in his array.

Input:

The first line contains T indicating test cases.Second line contains 2 integers N indicating the number of elements in his array and K.

Third line contains N space separated integers denoting Chandan array.

Output:

The minimum cost required to get K equal elements.

Constraints :

1 ≤ T ≤ 100

1 ≤ K ≤ N ≤100

1 ≤ A[i] ≤100

SAMPLE INPUT
1
5 3
9 4 9 7 4 

SAMPLE OUTPUT
6

Explanation

We can convert 7 to 9 to get three 9. The cost of this conversion will be 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 Mobius function - an important function in number theory. For each given n, it only has 3 values:
```
0  -- if n divisible by square of a prime. Such as: 4, 8, 9
1  -- if n not divisible by any square of a prime 
        and have even number of prime factor. Such as: 6, 10, 21
-1 -- otherwise. Such as: 3, 5, 7, 30```
Your task is to find mobius(`n`)

# Input/Output


 - `[input]` integer `n`


 `2 <= n <= 1e12`


 - `[output]` an integer

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day Vasya heard a story: "In the city of High Bertown a bus number 62 left from the bus station. It had *n* grown-ups and *m* kids..."

The latter events happen to be of no importance to us. Vasya is an accountant and he loves counting money. So he wondered what maximum and minimum sum of money these passengers could have paid for the ride.

The bus fare equals one berland ruble in High Bertown. However, not everything is that easy — no more than one child can ride for free with each grown-up passenger. That means that a grown-up passenger who rides with his *k* (*k*<=&gt;<=0) children, pays overall *k* rubles: a ticket for himself and (*k*<=-<=1) tickets for his children. Also, a grown-up can ride without children, in this case he only pays one ruble.

We know that in High Bertown children can't ride in a bus unaccompanied by grown-ups.

Help Vasya count the minimum and the maximum sum in Berland rubles, that all passengers of this bus could have paid in total.

Input Specification:
The input file consists of a single line containing two space-separated numbers *n* and *m* (0<=≤<=*n*,<=*m*<=≤<=105) — the number of the grown-ups and the number of the children in the bus, correspondingly.

Output Specification:
If *n* grown-ups and *m* children could have ridden in the bus, then print on a single line two space-separated integers — the minimum and the maximum possible total bus fare, correspondingly. 

Otherwise, print "Impossible" (without the quotes).

Demo Input:
['1 2\n', '0 5\n', '2 2\n']

Demo Output:
['2 2', 'Impossible', '2 3']

Note:
In the first sample a grown-up rides with two children and pays two rubles.

In the second sample there are only children in the bus, so the situation is impossible.
 In the third sample there are two cases: -  Each of the two grown-ups rides with one children and pays one ruble for the tickets. In this case the passengers pay two rubles in total. -  One of the grown-ups ride with two children's and pays two rubles, the another one rides alone and pays one ruble for himself. So, they pay three rubles in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dima took up the biology of bacteria, as a result of his experiments, he invented k types of bacteria. Overall, there are n bacteria at his laboratory right now, and the number of bacteria of type i equals c_{i}. For convenience, we will assume that all the bacteria are numbered from 1 to n. The bacteria of type c_{i} are numbered from $(\sum_{k = 1}^{i - 1} c_{k}) + 1$ to $\sum_{k = 1}^{i} c_{k}$.

With the help of special equipment Dima can move energy from some bacteria into some other one. Of course, the use of such equipment is not free. Dima knows m ways to move energy from some bacteria to another one. The way with number i can be described with integers u_{i}, v_{i} and x_{i} mean that this way allows moving energy from bacteria with number u_{i} to bacteria with number v_{i} or vice versa for x_{i} dollars.

Dima's Chef (Inna) calls the type-distribution correct if there is a way (may be non-direct) to move energy from any bacteria of the particular type to any other bacteria of the same type (between any two bacteria of the same type) for zero cost.

As for correct type-distribution the cost of moving the energy depends only on the types of bacteria help Inna to determine is the type-distribution correct? If it is, print the matrix d with size k × k. Cell d[i][j] of this matrix must be equal to the minimal possible cost of energy-moving from bacteria with type i to bacteria with type j.


-----Input-----

The first line contains three integers n, m, k (1 ≤ n ≤ 10^5; 0 ≤ m ≤ 10^5; 1 ≤ k ≤ 500). The next line contains k integers c_1, c_2, ..., c_{k} (1 ≤ c_{i} ≤ n). Each of the next m lines contains three integers u_{i}, v_{i}, x_{i} (1 ≤ u_{i}, v_{i} ≤ 10^5; 0 ≤ x_{i} ≤ 10^4). It is guaranteed that $\sum_{i = 1}^{k} c_{i} = n$.


-----Output-----

If Dima's type-distribution is correct, print string «Yes», and then k lines: in the i-th line print integers d[i][1], d[i][2], ..., d[i][k] (d[i][i] = 0). If there is no way to move energy from bacteria i to bacteria j appropriate d[i][j] must equal to -1. If the type-distribution isn't correct print «No».


-----Examples-----
Input
4 4 2
1 3
2 3 0
3 4 0
2 4 1
2 1 2

Output
Yes
0 2
2 0

Input
3 1 2
2 1
1 2 0

Output
Yes
0 -1
-1 0

Input
3 2 2
2 1
1 2 0
2 3 1

Output
Yes
0 1
1 0

Input
3 0 2
1 2

Output
No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In genetic the reverse complement of a sequence is formed by **reversing** the sequence and then taking the complement of each symbol.

The four nucleotides in DNA is Adenine (A), Cytosine (C), Guanine (G) and Thymine (Thymine). 

- A is the complement of T 
- C is the complement of G.

This is a bi-directional relation so:

- T is the complement of A
- G is the complement of C.

For this kata you need to complete the reverse complement function that take a DNA string and return the reverse complement string.

**Note**: You need to take care of lower and upper case. And if a sequence conatains some invalid characters you need to return "Invalid sequence".

This kata is based on the following [one](http://www.codewars.com/kata/complementary-dna/ruby) but with a little step in addition.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mary Ice is a member of a spy group. She is about to carry out a secret operation with her colleague.

She has got into a target place just now, but unfortunately the colleague has not reached there yet. She needs to hide from her enemy George Water until the colleague comes. Mary may want to make herself appear in George’s sight as short as possible, so she will give less chance for George to find her.

You are requested to write a program that calculates the time Mary is in George’s sight before her colleague arrives, given the information about moves of Mary and George as well as obstacles blocking their sight.

Read the Input section for the details of the situation.



Input

The input consists of multiple datasets. Each dataset has the following format:

Time R
L
MaryX1 MaryY1 MaryT1
MaryX2 MaryY2 MaryT2
...
MaryXL MaryYL MaryTL
M
GeorgeX1 GeorgeY1 GeorgeT1
GeorgeX2 GeorgeY2 GeorgeT2
...
GeorgeXM GeorgeYM GeorgeTM
N BlockSX1 BlockSY1 BlockTX1 BlockTY1
BlockSX2 BlockSY2 BlockTX2 BlockTY2
...
BlockSXN BlockSYN BlockTXN BlockTYN


The first line contains two integers. Time (0 ≤ Time ≤ 100) is the time Mary's colleague reaches the place. R (0 < R < 30000) is the distance George can see - he has a sight of this distance and of 45 degrees left and right from the direction he is moving. In other words, Mary is found by him if and only if she is within this distance from him and in the direction different by not greater than 45 degrees from his moving direction and there is no obstacles between them.

The description of Mary's move follows. Mary moves from (MaryXi, MaryYi) to (MaryXi+1, MaryYi+1) straight and at a constant speed during the time between MaryTi and MaryTi+1, for each 1 ≤ i ≤ L - 1. The following constraints apply: 2 ≤ L ≤ 20, MaryT1 = 0 and MaryTL = Time, and MaryTi < MaryTi+1 for any 1 ≤ i ≤ L - 1.

The description of George's move is given in the same way with the same constraints, following Mary's. In addition, (GeorgeXj, GeorgeYj ) and (GeorgeXj+1, GeorgeYj+1) do not coincide for any 1 ≤ j ≤ M - 1. In other words, George is always moving in some direction.

Finally, there comes the information of the obstacles. Each obstacle has a rectangular shape occupying (BlockSXk, BlockSYk) to (BlockTXk, BlockTYk). No obstacle touches or crosses with another. The number of obstacles ranges from 0 to 20 inclusive.

All the coordinates are integers not greater than 10000 in their absolute values. You may assume that, if the coordinates of Mary's and George's moves would be changed within the distance of 10-6, the solution would be changed by not greater than 10-6.

The last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed.

Output

For each dataset, print the calculated time in a line. The time may be printed with any number of digits after the decimal point, but should be accurate to 10-4 .

Example

Input

50 100
2
50 50 0
51 51 50
2
0 0 0
1 1 50
0
0 0


Output

50

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A programming competition site AtCode regularly holds programming contests.
The next contest on AtCode is called ABC, which is rated for contestants with ratings less than 1200.
The contest after the ABC is called ARC, which is rated for contestants with ratings less than 2800.
The contest after the ARC is called AGC, which is rated for all contestants.
Takahashi's rating on AtCode is R. What is the next contest rated for him?

-----Constraints-----
 - 0 ≤ R ≤ 4208
 - R is an integer.

-----Input-----
Input is given from Standard Input in the following format:
R

-----Output-----
Print the name of the next contest rated for Takahashi (ABC, ARC or AGC).

-----Sample Input-----
1199

-----Sample Output-----
ABC

1199 is less than 1200, so ABC will be rated.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:


Input Specification:
The input contains a single floating-point number *x* with exactly 6 decimal places (0<=&lt;<=*x*<=&lt;<=5).

Output Specification:
Output two integers separated by a single space. Each integer should be between 1 and 10, inclusive. If several solutions exist, output any of them. Solution will exist for all tests.

Demo Input:
['1.200000\n', '2.572479\n', '4.024922\n']

Demo Output:
['3 2\n', '10 3\n', '9 9\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Students of Winter Informatics School are going to live in a set of houses connected by underground passages. Teachers are also going to live in some of these houses, but they can not be accommodated randomly. For safety reasons, the following must hold:

  * All passages between two houses will be closed, if there are no teachers in both of them. All other passages will stay open. 
  * It should be possible to travel between any two houses using the underground passages that are open. 
  * Teachers should not live in houses, directly connected by a passage. 



Please help the organizers to choose the houses where teachers will live to satisfy the safety requirements or determine that it is impossible.

Input

The first input line contains a single integer t — the number of test cases (1 ≤ t ≤ 10^5). 

Each test case starts with two integers n and m (2 ≤ n ≤ 3 ⋅ 10^5, 0 ≤ m ≤ 3 ⋅ 10^5) — the number of houses and the number of passages.

Then m lines follow, each of them contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v), describing a passage between the houses u and v. It is guaranteed that there are no two passages connecting the same pair of houses.

The sum of values n over all test cases does not exceed 3 ⋅ 10^5, and the sum of values m over all test cases does not exceed 3 ⋅ 10^5.

Output

For each test case, if there is no way to choose the desired set of houses, output "NO". Otherwise, output "YES", then the total number of houses chosen, and then the indices of the chosen houses in arbitrary order.

Examples

Input


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


Output


YES
2
1 3 
NO


Input


1
17 27
1 8
2 9
3 10
4 11
5 12
6 13
7 14
8 9
8 14
8 15
9 10
9 15
10 11
10 15
10 17
11 12
11 17
12 13
12 16
12 17
13 14
13 16
14 16
14 15
15 16
15 17
16 17


Output


YES
8
1 3 4 5 6 9 14 17 

Note

The picture below shows the second example test. 

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are playing a new famous fighting game: Kortal Mombat XII. You have to perform a brutality on your opponent's character.

You are playing the game on the new generation console so your gamepad have $26$ buttons. Each button has a single lowercase Latin letter from 'a' to 'z' written on it. All the letters on buttons are pairwise distinct.

You are given a sequence of hits, the $i$-th hit deals $a_i$ units of damage to the opponent's character. To perform the $i$-th hit you have to press the button $s_i$ on your gamepad. Hits are numbered from $1$ to $n$.

You know that if you press some button more than $k$ times in a row then it'll break. You cherish your gamepad and don't want to break any of its buttons.

To perform a brutality you have to land some of the hits of the given sequence. You are allowed to skip any of them, however changing the initial order of the sequence is prohibited. The total damage dealt is the sum of $a_i$ over all $i$ for the hits which weren't skipped.

Note that if you skip the hit then the counter of consecutive presses the button won't reset.

Your task is to skip some hits to deal the maximum possible total damage to the opponent's character and not break your gamepad buttons.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the number of hits and the maximum number of times you can push the same button in a row.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the damage of the $i$-th hit.

The third line of the input contains the string $s$ consisting of exactly $n$ lowercase Latin letters — the sequence of hits (each character is the letter on the button you need to press to perform the corresponding hit).


-----Output-----

Print one integer $dmg$ — the maximum possible damage to the opponent's character you can deal without breaking your gamepad buttons.


-----Examples-----
Input
7 3
1 5 16 18 7 2 10
baaaaca

Output
54

Input
5 5
2 4 1 3 1000
aaaaa

Output
1010

Input
5 4
2 4 1 3 1000
aaaaa

Output
1009

Input
8 1
10 15 2 1 4 8 15 16
qqwweerr

Output
41

Input
6 3
14 18 9 19 2 15
cccccc

Output
52

Input
2 1
10 10
qq

Output
10



-----Note-----

In the first example you can choose hits with numbers $[1, 3, 4, 5, 6, 7]$ with the total damage $1 + 16 + 18 + 7 + 2 + 10 = 54$.

In the second example you can choose all hits so the total damage is $2 + 4 + 1 + 3 + 1000 = 1010$.

In the third example you can choose all hits expect the third one so the total damage is $2 + 4 + 3 + 1000 = 1009$.

In the fourth example you can choose hits with numbers $[2, 3, 6, 8]$. Only this way you can reach the maximum total damage $15 + 2 + 8 + 16 = 41$.

In the fifth example you can choose only hits with numbers $[2, 4, 6]$ with the total damage $18 + 19 + 15 = 52$.

In the sixth example you can change either first hit or the second hit (it does not matter) with the total damage $10$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a date, return the corresponding day of the week for that date.
The input is given as three integers representing the day, month and year respectively.
Return the answer as one of the following values {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}.
 
Example 1:
Input: day = 31, month = 8, year = 2019
Output: "Saturday"

Example 2:
Input: day = 18, month = 7, year = 1999
Output: "Sunday"

Example 3:
Input: day = 15, month = 8, year = 1993
Output: "Sunday"

 
Constraints:

The given dates are valid dates between the years 1971 and 2100.

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