vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: University Classes

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* student groups at the university. During the study day, each group can take no more than 7 classes. Seven time slots numbered from 1 to 7 are allocated for the classes.

The schedule on Monday is known for each group, i. e. time slots when group will have classes are known.

Your task is to determine the minimum number of rooms needed to hold classes for all groups on Monday. Note that one room can hold at most one group class in a single time slot.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=1000) — the number of groups. 

Each of the following *n* lines contains a sequence consisting of 7 zeroes and ones — the schedule of classes on Monday for a group. If the symbol in a position equals to 1 then the group has class in the corresponding time slot. In the other case, the group has no class in the corresponding time slot.

Output Specification:
Print minimum number of rooms needed to hold all groups classes on Monday.

Demo Input:
['2\n0101010\n1010101\n', '3\n0101011\n0011001\n0110111\n']

Demo Output:
['1\n', '3\n']

Note:
In the first example one room is enough. It will be occupied in each of the seven time slot by the first group or by the second group.

In the second example three rooms is enough, because in the seventh time slot all three groups have classes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a boolean function of three variables which is defined by its truth table. You need to find an expression of minimum length that equals to this function. The expression may consist of:   Operation AND ('&', ASCII code 38)  Operation OR ('|', ASCII code 124)  Operation NOT ('!', ASCII code 33)  Variables x, y and z (ASCII codes 120-122)  Parentheses ('(', ASCII code 40, and ')', ASCII code 41) 

If more than one expression of minimum length exists, you should find the lexicographically smallest one.

Operations have standard priority. NOT has the highest priority, then AND goes, and OR has the lowest priority. The expression should satisfy the following grammar:

E ::= E '|' T | T

T ::= T '&' F | F

F ::= '!' F | '(' E ')' | 'x' | 'y' | 'z'


-----Input-----

The first line contains one integer n — the number of functions in the input (1 ≤ n ≤ 10 000).

The following n lines contain descriptions of functions, the i-th of them contains a string of length 8 that consists of digits 0 and 1 — the truth table of the i-th function. The digit on position j (0 ≤ j < 8) equals to the value of the function in case of $x = \lfloor \frac{j}{4} \rfloor$, $y = \lfloor \frac{j}{2} \rfloor \operatorname{mod} 2$ and $z = j \operatorname{mod} 2$.


-----Output-----

You should output n lines, the i-th line should contain the expression of minimum length which equals to the i-th function. If there is more than one such expression, output the lexicographically smallest of them. Expressions should satisfy the given grammar and shouldn't contain white spaces.


-----Example-----
Input
4
00110011
00000111
11110000
00011111

Output
y
(y|z)&x
!x
x|y&z



-----Note-----

The truth table for the second function:

[Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a array a[] of non-negative integers. Count the number of pairs (i, j) in the array such that a[i] + a[j] < a[i]*a[j]. (the pair (i, j) and (j, i) are considered same and i should not be equal to j)
Example 1:
Input:
N=3
arr[] = {3, 4, 5} 
Output: 3
Explanation: Pairs are (3, 4) , (4, 5) and (3,5).  
 
Example 2:
Input:
N=3
arr[] = {1, 1, 1 } 
Output: 0
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function CountPairs() that takes array arr and integer n as parameters and return the total number of pairs possible.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{5}

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

Given an `n x n` array, return the array elements arranged from outermost elements to the middle element, traveling clockwise.

```
array = [[1,2,3],
         [4,5,6],
         [7,8,9]]
snail(array) #=> [1,2,3,6,9,8,7,4,5]
```

For better understanding, please follow the numbers of the next array consecutively:

```
array = [[1,2,3],
         [8,9,4],
         [7,6,5]]
snail(array) #=> [1,2,3,4,5,6,7,8,9]
```

This image will illustrate things more clearly:



NOTE: The idea is not sort the elements from the lowest value to the highest; the idea is to traverse the 2-d array in a clockwise snailshell pattern.

NOTE 2: The 0x0 (empty matrix) is represented as en empty array inside an array `[[]]`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In number world, two different numbers are friends if they have a lot in common, but also each one has unique perks.

More precisely, two different numbers $a$ and $b$ are friends if $gcd(a,b)$, $\frac{a}{gcd(a,b)}$, $\frac{b}{gcd(a,b)}$ can form sides of a triangle.

Three numbers $a$, $b$ and $c$ can form sides of a triangle if $a + b > c$, $b + c > a$ and $c + a > b$.

In a group of numbers, a number is lonely if it doesn't have any friends in that group.

Given a group of numbers containing all numbers from $1, 2, 3, ..., n$, how many numbers in that group are lonely?


-----Input-----

The first line contains a single integer $t$ $(1 \leq t \leq 10^6)$ - number of test cases.

On next line there are $t$ numbers, $n_i$ $(1 \leq n_i \leq 10^6)$ - meaning that in case $i$ you should solve for numbers $1, 2, 3, ..., n_i$.


-----Output-----

For each test case, print the answer on separate lines: number of lonely numbers in group $1, 2, 3, ..., n_i$.


-----Example-----
Input
3
1 5 10

Output
1
3
3



-----Note-----

For first test case, $1$ is the only number and therefore lonely.

For second test case where $n=5$, numbers $1$, $3$ and $5$ are lonely.

For third test case where $n=10$, numbers $1$, $5$ and $7$ are lonely.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mishka received a gift of multicolored pencils for his birthday! Unfortunately he lives in a monochrome world, where everything is of the same color and only saturation differs. This pack can be represented as a sequence a_1, a_2, ..., a_{n} of n integer numbers — saturation of the color of each pencil. Now Mishka wants to put all the mess in the pack in order. He has an infinite number of empty boxes to do this. He would like to fill some boxes in such a way that:

  Each pencil belongs to exactly one box;  Each non-empty box has at least k pencils in it;  If pencils i and j belong to the same box, then |a_{i} - a_{j}| ≤ d, where |x| means absolute value of x. Note that the opposite is optional, there can be pencils i and j such that |a_{i} - a_{j}| ≤ d and they belong to different boxes. 

Help Mishka to determine if it's possible to distribute all the pencils into boxes. Print "YES" if there exists such a distribution. Otherwise print "NO".


-----Input-----

The first line contains three integer numbers n, k and d (1 ≤ k ≤ n ≤ 5·10^5, 0 ≤ d ≤ 10^9) — the number of pencils, minimal size of any non-empty box and maximal difference in saturation between any pair of pencils in the same box, respectively.

The second line contains n integer numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — saturation of color of each pencil.


-----Output-----

Print "YES" if it's possible to distribute all the pencils into boxes and satisfy all the conditions. Otherwise print "NO".


-----Examples-----
Input
6 3 10
7 2 7 7 4 2

Output
YES

Input
6 2 3
4 5 3 13 4 10

Output
YES

Input
3 2 5
10 16 22

Output
NO



-----Note-----

In the first example it is possible to distribute pencils into 2 boxes with 3 pencils in each with any distribution. And you also can put all the pencils into the same box, difference of any pair in it won't exceed 10.

In the second example you can split pencils of saturations [4, 5, 3, 4] into 2 boxes of size 2 and put the remaining ones into another box.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of items, the i'th index element denotes the item id’s and given a number m, the task is to remove m elements such that there should be minimum distinct id’s left. Print the number of distinct id’s.
Example 1 -
Input:
n = 6
arr[] = {2, 2, 1, 3, 3, 3}
m = 3
Output:
1
Explanation : 
Remove 2,2,1
Example 2 -
Input:
n = 8
arr[] = {2, 4, 1, 5, 3, 5, 1, 3}
m = 2
Output:
3
Explanation:
Remove 2,4
Your Task:
This is a function problem. You don't have to take any input. Your task is to complete the distinctIds() which takes sorted array, its size n, and m as its parameter. You only need to find the minimum number of distinct IDs and return it. The driver code will print the returned value.
Expected Time Complexity: O(n log(n))
Expected Auxillary Space: O(n)
Constraints:
1 ≤ n ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{6}
1 ≤ m ≤ 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sergey recently learned about country codes - two letter strings, denoting countries. For example, BY stands for Belarus and IN stands for India. Mesmerized by this new discovery, Sergey now looks for country codes everywhere!
Sergey has recently found a string S consisting of uppercase Latin letters. He wants to find the number of different country codes that appear in S as contiguous substrings. For the purpose of this problem, consider that every 2-letter uppercase string is a valid country code.

-----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 and only line of each test case contains a string S, consisting of uppercase Latin letters.

-----Output-----
For each test case, output a single line containing the number of different country codes appearing in the given string.

-----Constraints-----

- 1 ≤ T ≤ 100
- Subtask 1 (35 points): 2 ≤ |S| ≤ 3
- Subtask 2 (65 points): 2 ≤ |S| ≤ 104

-----Example-----
Input:2
INBY
BYBY

Output:3
2

-----Explanation-----
Example case 1. The codes are IN, NB and BY.
Example case 2. The codes are BY and YB.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This function should take two string parameters: a person's name (`name`) and a quote of theirs (`quote`), and return a string attributing the quote to the person in the following format:

```python
'[name] said: "[quote]"'
```

For example, if `name` is `'Grae'` and `'quote'` is `'Practice makes perfect'` then your function should return the string
```python
'Grae said: "Practice makes perfect"'
```
Unfortunately, something is wrong with the instructions in the function body. Your job is to fix it so the function returns correctly formatted quotes.

Click the "Train" button to get started, and be careful with your quotation marks.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 You have set an alarm for some of the week days.
 
 Days of the week are encoded in binary representation like this:
```
0000001 - Sunday
0000010 - Monday
0000100 - Tuesday
0001000 - Wednesday
0010000 - Thursday
0100000 - Friday 
1000000 - Saturday```
For example, if your alarm is set only for Sunday and Friday, the representation will be `0100001`. 

 Given the current day of the week, your task is to find the day of the week when alarm will ring next time.

# Example

 For `currentDay = 4, availableWeekDays = 42`, the result should be `6`.
 
 ```
currentDay = 4 means the current Day is Wednesday
availableWeekDays = 42 convert to binary is "0101010"
So the next day is 6 (Friday)
```

# Input/Output


 - `[input]` integer `currentDay`
 
 The weekdays range from 1 to 7, 1 is Sunday and 7 is Saturday


 - `[input]` integer `availableWeekDays`
 
 An integer. Days of the week are encoded in its binary representation.


 - `[output]` an integer

 The next day available.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Let F(X) equals to the number of lucky digits in decimal representation of X. Chef wants to know the number of such integers X, that L ≤ X ≤ R and F(X) is a lucky number. Help him and calculate that number modulo 109+7.

-----Input-----
First line contains one integer T, the number of test cases. Each of the following T lines contains two space separated positive integers L and R.

-----Output-----
For each of the T test cases print one integer, the number of such X, that L ≤ X ≤ R and F(X) is a lucky number, modulo 1000000007.

-----Constraints-----

1 ≤ T ≤ 10

1 ≤ L ≤ R ≤ 101000

-----Example-----
Input:
4
1 100
1 10000
1 100000
4444 4447

Output:
0
16
640
2

-----Notes-----
First test case: of course, any number of less than 4 digits can't contain lucky number of lucky digits, so the answer is 0.

Second test case: 16 required numbers are 4444 4447 4474 4477 4744 4747 4774 4777 7444 7447 7474 7477 7744 7747 7774 7777.

Third test case: there are 640 required lucky numbers. Some of them are 4474, 14747, 41474, 77277, 44407, 74749.

Fourth test case: the only two required numbers are 4444 and 4447.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given the value of n, print the n'th prime number.

Input : A single integer n. 
Output : A single number which is the n'th prime number.
Constraints : 
1 ≤ n ≤ 1000

SAMPLE INPUT
2

SAMPLE OUTPUT
3

Explanation

The first few prime numbers are:
2,3,5,7. So, the answer is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your friend has been out shopping for puppies (what a time to be alive!)... He arrives back with multiple dogs, and you simply do not know how to respond!

By repairing the function provided, you will find out exactly how you should respond, depending on the number of dogs he has.

The number of dogs will always be a number and there will always be at least 1 dog.

```r
The expected behaviour is as follows:
- Your friend has fewer than 10 dogs:                    "Hardly any"
- Your friend has at least 10 but fewer than 51 dogs:    "More than a handful!"
- Your friend has at least 51 but not exactly 101 dogs:  "Woah that's a lot of dogs!"
- Your friend has 101 dogs:                              "101 DALMATIANS!!!"

Your friend will always have between 1 and 101 dogs, inclusive.
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a side length `n`, traveling only right and down how many ways are there to get from the top left corner to the bottom right corner of an `n by n` grid?

Your mission is to write a program to do just that!

Add code to `route(n)` that returns the number of routes for a grid `n by n` (if n is less than 1 return 0).

Examples:
    
    -100 -> 0
    
    1 -> 2
     
    2 -> 6
     
    20 -> 137846528820
    
Note: 
you're traveling on the edges of the squares in the grid not the squares themselves.

PS.If anyone has any suggestions of how to improve this kata please let me know.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Joseph really likes the culture of Japan. Last year he learned Japanese traditional clothes and visual arts and now he is trying to find out the secret of the Japanese game called Nonogram.

In the one-dimensional version of the game, there is a row of n empty cells, some of which are to be filled with a pen. There is a description of a solution called a profile — a sequence of positive integers denoting the lengths of consecutive sets of filled cells. For example, the profile of [4, 3, 1] means that there are sets of four, three, and one filled cell, in that order, with at least one empty cell between successive sets.

<image>

A suitable solution for n = 12 and p = [4, 3, 1]. 

<image>

A wrong solution: the first four filled cells should be consecutive. 

<image>

A wrong solution: there should be at least one empty cell before the last filled cell. 

Joseph found out that for some numbers n and profiles p there are lots of ways to fill the cells to satisfy the profile. Now he is in the process of solving a nonogram consisting of n cells and a profile p. He has already created a mask of p — he has filled all the cells that must be filled in every solution of the nonogram.

<image>

The mask for n = 12 and p = [4, 3, 1]: all the filled cells above are filled in every solution. 

After a break, he lost the source profile p. He only has n and the mask m. Help Joseph find any profile p' with the mask m or say that there is no such profile and Joseph has made a mistake.

Input

The only line contains a string m — the mask of the source profile p. The length of m is n (1 ≤ n ≤ 100 000). The string m consists of symbols # and _ — denoting filled and empty cells respectively.

Output

If there is no profile with the mask m, output the number -1. Otherwise, on the first line, output an integer k — the number of integers in the profile p'. On the second line, output k integers of the profile p'.

Examples

Input


__#_____


Output


2
3 2 


Input


_#


Output


-1


Input


___


Output


0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number N in the form of string, your task is to find the remainder when the number is divided by 7.
Note: The given number is very large and so the Input is taken as a String.
 
Example 1:
Input:
N = "98"
Output:
0
Explanation:
98 when divided by 7 gives a
remainder of 0.
Example 2:
Input:
N = "13"
Output:
6
Explanation:
13 when divided by 7 gives a
remainder of 6.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function findRemainder() which takes a String N as input and returns the answer.
 
Expected Time Complexity: O(|N|)
Expected Auxiliary Space: O(|N|)
 
Constraints:
0 <= |N| <= 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every year Santa Claus gives gifts to all children. However, each country has its own traditions, and this process takes place in different ways. For example, in Berland you need to solve the New Year's puzzle.

Polycarp got the following problem: given a grid strip of size 2 × n, some cells of it are blocked. You need to check if it is possible to tile all free cells using the 2 × 1 and 1 × 2 tiles (dominoes).

For example, if n = 5 and the strip looks like this (black cells are blocked):

<image>

Then it can be tiled, for example, using two vertical and two horizontal tiles, as in the picture below (different tiles are marked by different colors).

<image>

And if n = 3 and the strip looks like this:

<image>

It is impossible to tile free cells.

Polycarp easily solved this task and received his New Year's gift. Can you solve it?

Input

The first line contains an integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

Each test case is preceded by an empty line.

The first line of each test case contains two integers n and m (1 ≤ n ≤ 10^9, 1 ≤ m ≤ 2 ⋅ 10^5) — the length of the strip and the number of blocked cells on it.

Each of the next m lines contains two integers r_i, c_i (1 ≤ r_i ≤ 2, 1 ≤ c_i ≤ n) — numbers of rows and columns of blocked cells. It is guaranteed that all blocked cells are different, i.e. (r_i, c_i) ≠ (r_j, c_j), i ≠ j.

It is guaranteed that the sum of m over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, print on a separate line: 

  * "YES", if it is possible to tile all unblocked squares with the 2 × 1 and 1 × 2 tiles; 
  * "NO" otherwise. 



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

Example

Input


3

5 2
2 2
1 4

3 2
2 1
2 3

6 4
2 1
2 3
2 4
2 6


Output


YES
NO
NO

Note

The first two test cases are explained in the statement.

In the third test case the strip looks like this: 

<image> It is easy to check that the unblocked squares on it can not be tiled.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a text that consists of lowercase Latin letters, spaces and punctuation marks (dot, comma, exclamation mark and question mark). A word is defined as a sequence of consecutive Latin letters.

Your task is to add spaces to the text by the following rules:
 -  if there is no punctuation mark between two words, then they should be separated by exactly one space -  there should be no spaces before each punctuation mark -  there should be exactly one space after each punctuation mark 
It is guaranteed that there is at least one word between any two punctuation marks. The text begins and ends with a Latin letter.

Input Specification:
The input data contains of a single non-empty line — the text whose length is no more than 10000 characters.

Output Specification:
Print the text, edited according to the rules. In this problem you should follow the output format very strictly. For example, extra space at the end of the output line is considered as wrong answer. Note that a newline character at the end of the line doesn't matter.

Demo Input:
['galileo galilei was an   italian physicist  ,mathematician,astronomer\n', 'galileo  was  born  in  pisa\n']

Demo Output:
['galileo galilei was an italian physicist, mathematician, astronomer\n', 'galileo was born in pisa\n']

Note:
none

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