vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Akshara is a Maths teacher at Dynamic Public School.One day she decided to take an unusual test of all her students.She took all her students to a fair.There she took them to a candy room.The room had 2 doors and behind each door was unlimited supply of candies.The excitement of the students could not be measured.Each student wanted a specific amount of candies.Now here was the test.

At a time 1 student could enter 1 door.After he exits another will enter.No time is lost when there is change of students.For proccessing 1 candy it took 1 second.The teacher gave exactly X amount of time for all the students
to get their specific amount of candies.So the students ask you for help in determining whether it is possible for all the students to get their candies or not  in X amount of time.

Input:

The first line contains T denoting the number of test cases.Each testcase consist of two lines containing n and x denoting the number of students and the time given by the teacher.The next line contains n space separated numbers denoting the amount of candy each student wants.

Output:

For each testcase print YES if it is possible or NO.

Constraints:

1 ≤ T ≤ 25

1 ≤ N ≤ 100

1 ≤ x ≤ 100000

0 ≤ A[i] ≤ 100

SAMPLE INPUT
2
3 4
2 4 2
3 3
3 3 3


SAMPLE OUTPUT
YES
NO

Explanation

In the first testcase:

At t=0 Student 3 enters door 1 and student 2 enters door 2.

At t=2 Student 1 enters door 1 and student 3 exits.

At t=4 Student 2 and 1 exits.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"We've tried solitary confinement, waterboarding and listening to Just In Beaver, to no avail. We need something extreme."

"Little Alena got an array as a birthday present..."

The array b of length n is obtained from the array a of length n and two integers l and r (l ≤ r) using the following procedure:

b_1 = b_2 = b_3 = b_4 = 0.

For all 5 ≤ i ≤ n:   b_{i} = 0 if a_{i}, a_{i} - 1, a_{i} - 2, a_{i} - 3, a_{i} - 4 > r and b_{i} - 1 = b_{i} - 2 = b_{i} - 3 = b_{i} - 4 = 1  b_{i} = 1 if a_{i}, a_{i} - 1, a_{i} - 2, a_{i} - 3, a_{i} - 4 < l and b_{i} - 1 = b_{i} - 2 = b_{i} - 3 = b_{i} - 4 = 0  b_{i} = b_{i} - 1 otherwise 

You are given arrays a and b' of the same length. Find two integers l and r (l ≤ r), such that applying the algorithm described above will yield an array b equal to b'.

It's guaranteed that the answer exists.


-----Input-----

The first line of input contains a single integer n (5 ≤ n ≤ 10^5) — the length of a and b'.

The second line of input contains n space separated integers a_1, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9) — the elements of a.

The third line of input contains a string of n characters, consisting of 0 and 1 — the elements of b'. Note that they are not separated by spaces.


-----Output-----

Output two integers l and r ( - 10^9 ≤ l ≤ r ≤ 10^9), conforming to the requirements described above.

If there are multiple solutions, output any of them.

It's guaranteed that the answer exists.


-----Examples-----
Input
5
1 2 3 4 5
00001

Output
6 15

Input
10
-10 -9 -8 -7 -6 6 7 8 9 10
0000111110

Output
-5 5



-----Note-----

In the first test case any pair of l and r pair is valid, if 6 ≤ l ≤ r ≤ 10^9, in that case b_5 = 1, because a_1, ..., a_5 < l.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Cady’s Chocolate Company just opened down the street! Cady’s chocolate is world famous, and her recipe is top secret. But the company is more renowned for the fact that they sell the chocolate in random quantities. Each box of chocolate may contain anywhere from $1$ to $100$ pieces.

Bob’s nephews, John and Sam, love Cady’s Chocolate, but Bob has a dilemma. John will get jealous of Sam if he gets more pieces of chocolate, and vice versa. Bob knows how many pieces of chocolate are in each box.

Write a program to help him determine if it is possible to split the boxes between John and Sam such that both get the same number of pieces of chocolate, and such that all boxes of chocolate are used.

-----Input-----
The input consists of a single test case. The first line contains an integer $n$ ($1 \le n \le 1000$), the number of boxes of chocolate Bob bought. The next line contains $n$ integers $a_ i$ representing the number of pieces of chocolate in the $i^{\text {th}}$ box ($1\le a_ i \le 100$).

-----Output-----
If it is possible for Bob to split the boxes such that John and Sam get the same number of pieces of chocolate, output YES. Otherwise, output NO.

-----Examples-----
Sample Input:
6
1 4 3 12 13 1
Sample Output:
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Coming up with a new problem isn't as easy as many people think. Sometimes it is hard enough to name it. We'll consider a title original if it doesn't occur as a substring in any titles of recent Codeforces problems. 

You've got the titles of n last problems — the strings, consisting of lowercase English letters. Your task is to find the shortest original title for the new problem. If there are multiple such titles, choose the lexicographically minimum one. Note, that title of the problem can't be an empty string.

A substring s[l... r] (1 ≤ l ≤ r ≤ |s|) of string s = s_1s_2... s_{|}s| (where |s| is the length of string s) is string s_{l}s_{l} + 1... s_{r}.

String x = x_1x_2... x_{p} is lexicographically smaller than string y = y_1y_2... y_{q}, if either p < q and x_1 = y_1, x_2 = y_2, ... , x_{p} = y_{p}, or there exists such number r (r < p, r < q), that x_1 = y_1, x_2 = y_2, ... , x_{r} = y_{r} and x_{r} + 1 < y_{r} + 1. The string characters are compared by their ASCII codes.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 30) — the number of titles you've got to consider. Then follow n problem titles, one per line. Each title only consists of lowercase English letters (specifically, it doesn't contain any spaces) and has the length from 1 to 20, inclusive.


-----Output-----

Print a string, consisting of lowercase English letters — the lexicographically minimum shortest original title.


-----Examples-----
Input
5
threehorses
goodsubstrings
secret
primematrix
beautifulyear

Output
j

Input
4
aa
bdefghijklmn
opqrstuvwxyz
c

Output
ab



-----Note-----

In the first sample the first 9 letters of the English alphabet (a, b, c, d, e, f, g, h, i) occur in the problem titles, so the answer is letter j.

In the second sample the titles contain 26 English letters, so the shortest original title cannot have length 1. Title aa occurs as a substring in the first title.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array A of size N. The elements of the array consist of positive integers. You have to find the largest element with minimum frequency. 
Example 1:
Input: 
5
2 2 5 50 1
Output:
50
Explanation :
All elements are having frequency 1 except 2.
50 is the maximum element with minimum frequency.
Example 2:
Input:
4
3 3 5 5
Output:
5
Explanation:
Both 3 and 5 have the same frequency, so 5 should be returned.
User Task:
Your task is to complete the provided function LargButMinFreq(A, n) which accepts array A and n. Hence you have to return the largest element with minimum frequency.
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
Constraints:
1 <= N <= 10^{5}
1 <= A[i] <= 10^{6}

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

Time Limit: 1 seconds

Memory Limit: 64 megabytes

Problem Description:
Peter likes to travel by train. He likes it so much that on the train he falls asleep. 

Once in summer Peter was going by train from city A to city B, and as usual, was sleeping. Then he woke up, started to look through the window and noticed that every railway station has a flag of a particular colour.

The boy started to memorize the order of the flags' colours that he had seen. But soon he fell asleep again. Unfortunately, he didn't sleep long, he woke up and went on memorizing the colours. Then he fell asleep again, and that time he slept till the end of the journey.

At the station he told his parents about what he was doing, and wrote two sequences of the colours that he had seen before and after his sleep, respectively.

Peter's parents know that their son likes to fantasize. They give you the list of the flags' colours at the stations that the train passes sequentially on the way from A to B, and ask you to find out if Peter could see those sequences on the way from A to B, or from B to A. Remember, please, that Peter had two periods of wakefulness.

Peter's parents put lowercase Latin letters for colours. The same letter stands for the same colour, different letters — for different colours.

Input Specification:
The input data contains three lines. The first line contains a non-empty string, whose length does not exceed 105, the string consists of lowercase Latin letters — the flags' colours at the stations on the way from A to B. On the way from B to A the train passes the same stations, but in reverse order. 

The second line contains the sequence, written by Peter during the first period of wakefulness. The third line contains the sequence, written during the second period of wakefulness. Both sequences are non-empty, consist of lowercase Latin letters, and the length of each does not exceed 100 letters. Each of the sequences is written in chronological order.

Output Specification:
Output one of the four words without inverted commas: 
 -  «forward» — if Peter could see such sequences only on the way from A to B; -  «backward» — if Peter could see such sequences on the way from B to A; -  «both» — if Peter could see such sequences both on the way from A to B, and on the way from B to A; -  «fantasy» — if Peter could not see such sequences.

Demo Input:
['atob\na\nb\n', 'aaacaaa\naca\naa\n']

Demo Output:
['forward\n', 'both\n']

Note:
It is assumed that the train moves all the time, so one flag cannot be seen twice. There are no flags at stations A and B.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day Vasya got hold of a sheet of checkered paper n × m squares in size. Our Vasya adores geometrical figures, so he painted two rectangles on the paper. The rectangles' sides are parallel to the coordinates' axes, also the length of each side of each rectangle is no less than 3 squares and the sides are painted by the grid lines. The sides can also be part of the sheet of paper's edge. Then Vasya hatched all squares on the rectangles' frames.

Let's define a rectangle's frame as the set of squares inside the rectangle that share at least one side with its border.

A little later Vasya found a sheet of paper of exactly the same size and couldn't guess whether it is the same sheet of paper or a different one. So, he asked you to check whether the sheet of paper he had found contains two painted frames and nothing besides them.

Please note that the frames painted by Vasya can arbitrarily intersect, overlap or even completely coincide.

The coordinates on the sheet of paper are introduced in such a way that the X axis goes from top to bottom, the x coordinates of the squares' numbers take values from 1 to n and the Y axis goes from the left to the right and the y coordinates of the squares' numbers take values from 1 to m.

Input

The first input line contains two integers n and m (3 ≤ n, m ≤ 1000) — the sizes of the sheet of paper Vasya found. Next n lines, each consisting of m symbols "." (dot) and "#" (number sign), describe the found sheet of paper. The symbol "#" represents a hatched square and the symbol "." represents a non-hatched square.

Output

In the first line print the single word "YES" or "NO", meaning whether it is true that the found sheet of paper has two frames painted on it. If the answer is positive, then print in the second line 4 integers: the coordinates of the upper left and lower right corners of the first frame. In the third line print 4 integers: the coordinates of the upper left and the lower right corners of the second frame. If there are multiple answers, print any of them.

Examples

Input

4 5
#####
#.#.#
###.#
#####


Output

YES
1 1 3 3
1 1 4 5


Input

5 6
...###
...###
#####.
#...#.
#####.


Output

NO

Note

In the first sample there are two frames on the picture. The first one is:
    
    
    ###..  
    #.#..  
    ###..  
    .....  
    

The second one is:
    
    
    #####  
    #...#  
    #...#  
    #####  
    

In the second sample the painted figures are not frames. Note that the height and width of valid frames is no less than 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
IA has so many colorful magnets on her fridge! Exactly one letter is written on each magnet, 'a' or 'b'. She loves to play with them, placing all magnets in a row. However, the girl is quickly bored and usually thinks how to make her entertainment more interesting.

Today, when IA looked at the fridge, she noticed that the word formed by magnets is really messy. "It would look much better when I'll swap some of them!" — thought the girl — "but how to do it?". After a while, she got an idea. IA will look at all prefixes with lengths from $1$ to the length of the word and for each prefix she will either reverse this prefix or leave it as it is. She will consider the prefixes in the fixed order: from the shortest to the largest. She wants to get the lexicographically smallest possible word after she considers all prefixes. Can you help her, telling which prefixes should be chosen for reversing?

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds: $a$ is a prefix of $b$, but $a \ne b$; in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.


-----Input-----

The first and the only line contains a string $s$ ($1 \le |s| \le 1000$), describing the initial string formed by magnets. The string $s$ consists only of characters 'a' and 'b'.


-----Output-----

Output exactly $|s|$ integers. If IA should reverse the $i$-th prefix (that is, the substring from $1$ to $i$), the $i$-th integer should be equal to $1$, and it should be equal to $0$ otherwise.

If there are multiple possible sequences leading to the optimal answer, print any of them.


-----Examples-----
Input
bbab

Output
0 1 1 0

Input
aaaaa

Output
1 0 0 0 1



-----Note-----

In the first example, IA can reverse the second and the third prefix and get a string "abbb". She cannot get better result, since it is also lexicographically smallest string obtainable by permuting characters of the initial string.

In the second example, she can reverse any subset of prefixes — all letters are 'a'.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is playing a game with his childhood friend. He gave his friend a list of N numbers named $a_1, a_2 ....  a_N$ (Note: All numbers are unique). Adjust the numbers in the following order:
$(i)$ swap every alternate number with it's succeeding number (If N is odd, do not swap the last number i.e. $a_N$ ).
$(ii)$ add %3 of every number to itself.
$(iii)$ swap the ith number and the (N-i-1) th number.
After this, Chef will give a number to his friend and he has to give the nearest greater and smaller number to it.
If there is no greater or lesser number, put -1.
Help his friend to find the two numbers.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, an integers $N$. 
- Next line contains $N$ integers separated by a space. 
- Next line contains a number to be found, $M$. 

-----Output:-----
For each test case, output in a single line answer given the immediate smaller and greater number separated by a space.

-----Constraints-----
- $1 \leq T \leq 1000$
- $3 \leq N \leq 10^5$
- $1 \leq N_i \leq 10^9$
- $1 \leq M \leq 10^9$

-----Sample Input:-----
1
10
5 15 1 66 55 32 40 22 34 11
38

-----Sample Output:-----
35 41

-----Explaination:-----
Step 1: 15 5 66 1 32 55 22 40 11 34
Step 2: 15 7 66 2 34 56 23 41 13 35
Step 3: 35  13 41 23 56 34 2 66 7 15
35 is the number lesser than 38 and 41 is the number greater than 38 in the given set of numbers.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You managed to send your friend to queue for tickets in your stead, but there is a catch: he will get there only if you tell him how much that is going to take. And everybody can only take one ticket at a time, then they go back in the last position of the queue if they need more (or go home if they are fine).

Each ticket takes one minutes to emit, the queue is well disciplined, [Brit-style](https://www.codewars.com/kata/english-beggars), and so it moves smoothly, with no waste of time.

You will be given an array/list/vector with all the people queuing and the *initial* position of your buddy, so for example, knowing that your friend is in the third position (that we will consider equal to the index, `2`: he is the guy that wants 3 tickets!) and the initial queue is `[2, 5, 3, 4, 6]`.

The first dude gets his ticket and the queue goes now like this `[5, 3, 4, 6, 1]`, then `[3, 4, 6, 1, 4]` and so on. In the end, our buddy will be queuing for 12 minutes, true story!

Build a function to compute it, resting assured that only positive integers are going to be there and you will be always given a valid index; but we also want to go to pretty popular events, so be ready for big queues with people getting plenty of tickets.

[[hard core version](https://www.codewars.com/kata/queue-time-counter-hard-core-version/solutions/javascript) now available if you don't want the "easy" kata!]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string $s$ consisting of lowercase Latin letters "a", "b" and "c" and question marks "?".

Let the number of question marks in the string $s$ be $k$. Let's replace each question mark with one of the letters "a", "b" and "c". Here we can obtain all $3^{k}$ possible strings consisting only of letters "a", "b" and "c". For example, if $s = $"ac?b?c" then we can obtain the following strings: $[$"acabac", "acabbc", "acabcc", "acbbac", "acbbbc", "acbbcc", "accbac", "accbbc", "accbcc"$]$.

Your task is to count the total number of subsequences "abc" in all resulting strings. Since the answer can be very large, print it modulo $10^{9} + 7$.

A subsequence of the string $t$ is such a sequence that can be derived from the string $t$ after removing some (possibly, zero) number of letters without changing the order of remaining letters. For example, the string "baacbc" contains two subsequences "abc" — a subsequence consisting of letters at positions $(2, 5, 6)$ and a subsequence consisting of letters at positions $(3, 5, 6)$.


-----Input-----

The first line of the input contains one integer $n$ $(3 \le n \le 200\,000)$ — the length of $s$.

The second line of the input contains the string $s$ of length $n$ consisting of lowercase Latin letters "a", "b" and "c" and question marks"?".


-----Output-----

Print the total number of subsequences "abc" in all strings you can obtain if you replace all question marks with letters "a", "b" and "c", modulo $10^{9} + 7$.


-----Examples-----
Input
6
ac?b?c

Output
24

Input
7
???????

Output
2835

Input
9
cccbbbaaa

Output
0

Input
5
a???c

Output
46



-----Note-----

In the first example, we can obtain $9$ strings:  "acabac" — there are $2$ subsequences "abc",  "acabbc" — there are $4$ subsequences "abc",  "acabcc" — there are $4$ subsequences "abc",  "acbbac" — there are $2$ subsequences "abc",  "acbbbc" — there are $3$ subsequences "abc",  "acbbcc" — there are $4$ subsequences "abc",  "accbac" — there is $1$ subsequence "abc",  "accbbc" — there are $2$ subsequences "abc",  "accbcc" — there are $2$ subsequences "abc". 

So, there are $2 + 4 + 4 + 2 + 3 + 4 + 1 + 2 + 2 = 24$ subsequences "abc" in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive integer $n$, it is guaranteed that $n$ is even (i.e. divisible by $2$).

You want to construct the array $a$ of length $n$ such that:   The first $\frac{n}{2}$ elements of $a$ are even (divisible by $2$);  the second $\frac{n}{2}$ elements of $a$ are odd (not divisible by $2$);  all elements of $a$ are distinct and positive;  the sum of the first half equals to the sum of the second half ($\sum\limits_{i=1}^{\frac{n}{2}} a_i = \sum\limits_{i=\frac{n}{2} + 1}^{n} a_i$). 

If there are multiple answers, you can print any. It is not guaranteed that the answer exists.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the array. It is guaranteed that that $n$ is even (i.e. divisible by $2$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer — "NO" (without quotes), if there is no suitable answer for the given test case or "YES" in the first line and any suitable array $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) satisfying conditions from the problem statement on the second line.


-----Example-----
Input
5
2
4
6
8
10

Output
NO
YES
2 4 1 5
NO
YES
2 4 6 8 1 3 5 11
NO

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