vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Think about Zuma Game. You have a row of balls on the table, colored red(R), yellow(Y), blue(B), green(G), and white(W). You also have several balls in your hand.

Each time, you may choose a ball in your hand, and insert it into the row (including the leftmost place and rightmost place). Then, if there is a group of 3 or more balls in the same color touching, remove these balls. Keep doing this until no more balls can be removed.

Find the minimal balls you have to insert to remove all the balls on the table. If you cannot remove all the balls, output -1.


Examples:
Input: "WRRBBW", "RB"
Output: -1
Explanation: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW

Input: "WWRRBBWW", "WRBRW"
Output: 2
Explanation: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty

Input:"G", "GGGGG"
Output: 2
Explanation: G -> G[G] -> GG[G] -> empty 

Input: "RBYYBBRRB", "YRBGB"
Output: 3
Explanation: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty 



Note:

You may assume that the initial row of balls on the table won’t have any 3 or more consecutive balls with the same color.
The number of balls on the table won't exceed 20, and the string represents these balls is called "board" in the input.
The number of balls in your hand won't exceed 5, and the string represents these balls is called "hand" in the input.
Both input strings will be non-empty and only contain characters 'R','Y','B','G','W'.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
While resting on the ship after the "Russian Code Cup" a boy named Misha invented an interesting game. He promised to give his quadrocopter to whoever will be the first one to make a rectangular table of size *n*<=×<=*m*, consisting of positive integers such that the sum of the squares of numbers for each row and each column was also a square.

Since checking the correctness of the table manually is difficult, Misha asks you to make each number in the table to not exceed 108.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=100)  — the size of the table.

Output Specification:
Print the table that meets the condition: *n* lines containing *m* integers, separated by spaces. If there are multiple possible answers, you are allowed to print anyone. It is guaranteed that there exists at least one correct answer.

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

Demo Output:
['1', '3 4']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a convex polygon. Count, please, the number of triangles that contain a given point in the plane and their vertices are the vertices of the polygon. It is guaranteed, that the point doesn't lie on the sides and the diagonals of the polygon.

Input

The first line contains integer n — the number of vertices of the polygon (3 ≤ n ≤ 100000). The polygon description is following: n lines containing coordinates of the vertices in clockwise order (integer x and y not greater than 109 by absolute value). It is guaranteed that the given polygon is nondegenerate and convex (no three points lie on the same line).

The next line contains integer t (1 ≤ t ≤ 20) — the number of points which you should count the answer for. It is followed by t lines with coordinates of the points (integer x and y not greater than 109 by absolute value).

Output

The output should contain t integer numbers, each on a separate line, where i-th number is the answer for the i-th point.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

Examples

Input

4
5 0
0 0
0 5
5 5
1
1 3


Output

2


Input

3
0 0
0 5
5 0
2
1 1
10 10


Output

1
0


Input

5
7 6
6 3
4 1
1 2
2 4
4
3 3
2 3
5 5
4 2


Output

5
3
3
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an nxm board with a number between -1 and nxm in every entries.
And an nxm matrix M is also given, where M(i,j) is the cost of selecting the (i,j) entry of the given board.

Your task is to find a connected block (which means these entries can reach each other by just go up, down, left and right without going out the block) in the board that contains at least K distinct positive numbers without any -1, and it must have minimum total cost for selecting these entries. Output the minimum total cost.

INPUT

First line consists of three integers, n, m, K (1 ≤ n, m ≤ 15, 1 ≤ K ≤ 7).
Then follows are two n*m matrices, the first matrix denotes the numbers on the board and the second matrix denotes the cost of every entry.

Namely, the first n lines contain m integers, where the jth number in ith line denotes the number on the entry (i,j) of the board. These integers are in [-1, n*m].

Next n lines contain m integers too. The jth number in ith line denotes the cost of selecting the entry (i,j) of the board. These integers are in [1, 100000].

OUTPUT

Print only one line containing the minimum cost to finish the task. If the task is impossible, output -1 please.

SAMPLE INPUT
3 3 3
0 0 1
2 3 3
-1 2 1
3 1 5
4 10 1
9 3 4

SAMPLE OUTPUT
8

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Nikolay has *a* lemons, *b* apples and *c* pears. He decided to cook a compote. According to the recipe the fruits should be in the ratio 1:<=2:<=4. It means that for each lemon in the compote should be exactly 2 apples and exactly 4 pears. You can't crumble up, break up or cut these fruits into pieces. These fruits — lemons, apples and pears — should be put in the compote as whole fruits.

Your task is to determine the maximum total number of lemons, apples and pears from which Nikolay can cook the compote. It is possible that Nikolay can't use any fruits, in this case print 0.

Input Specification:
The first line contains the positive integer *a* (1<=≤<=*a*<=≤<=1000) — the number of lemons Nikolay has. 

The second line contains the positive integer *b* (1<=≤<=*b*<=≤<=1000) — the number of apples Nikolay has. 

The third line contains the positive integer *c* (1<=≤<=*c*<=≤<=1000) — the number of pears Nikolay has.

Output Specification:
Print the maximum total number of lemons, apples and pears from which Nikolay can cook the compote.

Demo Input:
['2\n5\n7\n', '4\n7\n13\n', '2\n3\n2\n']

Demo Output:
['7\n', '21\n', '0\n']

Note:
In the first example Nikolay can use 1 lemon, 2 apples and 4 pears, so the answer is 1 + 2 + 4 = 7.

In the second example Nikolay can use 3 lemons, 6 apples and 12 pears, so the answer is 3 + 6 + 12 = 21.

In the third example Nikolay don't have enough pears to cook any compote, so the answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After completing some serious investigation, Watson and Holmes are now chilling themselves in the Shimla hills. Very soon Holmes became bored. Holmes lived entirely for his profession. We know he is a workaholic. So Holmes wants to stop his vacation and get back to work. But after a tiresome season, Watson is in no mood to return soon. So to keep Holmes engaged, he decided to give Holmes one math problem. And Holmes agreed to solve the problem and said as soon as he solves the problem, they should return back to work. Watson too agreed. 
The problem was as follows. Watson knows Holmes’ favorite numbers are 6 and 5. So he decided to give Holmes N  single digit numbers. Watson asked Holmes to form a new number with the given N numbers in such a way that the newly formed number should be completely divisible by 5 and 6. Watson told Holmes that he should also form the number from these digits in such a way that the formed number is maximum. He may or may not use all the given numbers. But he is not allowed to use leading zeros. Though he is allowed to leave out some of the numbers, he is not allowed to add any extra numbers, which means the maximum count of each digit in the newly formed number, is the same as the number of times that number is present in those given N digits.

-----Input-----
The first line of input contains one integers T denoting the number of test cases.
Each test case consists of one integer N, number of numbers.
Next line contains contains N single digit integers 

-----Output-----
For each test case output a single number, where the above said conditions are satisfied. If it is not possible to create such a number with the given constraints print -1.If there exists a solution, the maximised number should be greater than or equal to 0. 

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 10000
- 0 ≤ Each digit ≤ 9

-----Subtasks-----
Subtask #1 : (90 points)
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 10000

Subtask 2 : (10 points) 

- 1 ≤ T ≤ 10
- 1 ≤ N≤ 10

-----Example-----
Input:
2
12
3 1 2 3 2 0 2 2 2 0 2 3
11
3 9 9 6 4 3 6 4 9 6 0

Output:
33322222200
999666330

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob just learned about bitwise operators. Since Alice is an expert, she decided to play a game, she will give a number $x$ to Bob and will ask some questions:
There will be 4 different kinds of queries:-
- 
Alice gives an integer $i$ and Bob has to report the status of the $i^{th}$ bit in $x$, the answer is $"ON"$ if it is on else $"OFF"$.
- 
Alice gives an integer $i$ and Bob has to turn on the $i^{th}$ bit in $x$.
- 
Alice gives an integer $i$ and Bob has to turn off the $i^{th}$ bit in $x$.
- 
Alice gives two integers $p$ and $q$ and in the binary representation of $x$ Bob has to swap the $p^{th}$ and the $q^{th}$ bits.
The value of $x$ changes after any update operation.
positions $i$, $p$, and $q$ are always counted from the right or from the least significant bit.
If anyone of $i$, $p$, or $q$ is greater than the number of bits in the binary representation of $x$, consider $0$ at that position.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- the first line of each test case contains two space-separated integers $x, Q$.
- $2Q$ lines follow.
- first line is an integer, the query type.
- for each query of type 1 to 3, there will be the integer $i$
- for the query of type 4, there will be two space-separated integers, the integers $p, q$

-----Output:-----
For the queries of the first kind, print $"ON"$ or $"OFF"$.

-----Constraints-----
- $1 \leq T \leq 10^3$
- $1 \leq x \leq 10^9$
- $1 \leq Q \leq 10^3$
- $1 \leq i,p,q \leq 30$

-----Sample Input-----
1
2 2
2 
1
1 
1

-----Sample Output:-----
ON

-----EXPLANATION:-----
the binary representation of 2 is 10
for query 1, we just have to update x to 11 (or 3 in decimal).
for the next query, x is now 3 or 11 in binary so the answer is ON.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Initially, you have the array $a$ consisting of one element $1$ ($a = [1]$).

In one move, you can do one of the following things:

  Increase some (single) element of $a$ by $1$ (choose some $i$ from $1$ to the current length of $a$ and increase $a_i$ by one);  Append the copy of some (single) element of $a$ to the end of the array (choose some $i$ from $1$ to the current length of $a$ and append $a_i$ to the end of the array). 

For example, consider the sequence of five moves:

  You take the first element $a_1$, append its copy to the end of the array and get $a = [1, 1]$.  You take the first element $a_1$, increase it by $1$ and get $a = [2, 1]$.  You take the second element $a_2$, append its copy to the end of the array and get $a = [2, 1, 1]$.  You take the first element $a_1$, append its copy to the end of the array and get $a = [2, 1, 1, 2]$.  You take the fourth element $a_4$, increase it by $1$ and get $a = [2, 1, 1, 3]$. 

Your task is to find the minimum number of moves required to obtain the array with the sum at least $n$.

You have to answer $t$ independent test cases.


-----Input-----

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

The only line of the test case contains one integer $n$ ($1 \le n \le 10^9$) — the lower bound on the sum of the array.


-----Output-----

For each test case, print the answer: the minimum number of moves required to obtain the array with the sum at least $n$.


-----Example-----
Input
5
1
5
42
1337
1000000000

Output
0
3
11
72
63244

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string S. S consists of several words separated by one or more spaces. Word consists of Latin letters as well as other symbols (but not spaces).
In each word which starts from lowercase Latin letter replace starting letter with uppercase Latin letter.

Input
The only line contains S

Output
Output one line with modified string S.

Constraints
1 ≤ length of S ≤ 30 000

SAMPLE INPUT
Wish you were here

SAMPLE OUTPUT
Wish You Were Here

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You get a new job working for Eggman Movers.  Your first task is to write a method that will allow the admin staff to enter a person’s name and return what that person's role is in the company.

You will be given an array of object literals holding the current employees of the company.  You code must find the employee with the matching firstName and lastName and then return the role for that employee or if no employee is not found it should return "Does not work here!"

The array is preloaded and can be referenced using the variable `employees` (`$employees` in Ruby). It uses the following structure.

```python
employees = [ {'first_name': "Dipper", 'last_name': "Pines", 'role': "Boss"}, ...... ]
```

There are no duplicate names in the array and the name passed in will be a single string with a space between the first and last name i.e. Jane Doe or just a name.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After your boat ran out of fuel in the middle of the ocean, you have been following the currents for 80 days. Today, you finally got your radar equipment working. And it’s receiving signals!

Alas, the signals come from the “radar” station owned by the eccentric lighthouse keeper Hasse. Hasse’s radar station (which does not work quite like other radar stations) emits continuous signals of three different wave-lengths. Therefore, the only interesting thing you can measure is the phase of a signal as it reaches you. For example, if the signal you tuned on to has a wave-length of $100$ meters and you are $1456$ meters from the station, your equipment can only tell you that you are either $56$, or $156$, or $256$, or $\dots $ meters away from the lighthouse.

So you reach for your last piece of paper to start calculating – but wait, there’s a catch! On the display you read: “ACCURACY: 3 METERS”. So, in fact, the information you get from this signal is that your distance from Hasse’s radar station is in the union of intervals $[53,59] \cup [153, 159] \cup [253, 259] \cup \dots $.

What to do? Since the key to surviving at sea is to be optimistic, you are interested in what the smallest possible distance to the lighthouse could be, given the wavelengths, measurements and accuracies corresponding to the three signals.

-----Task-----
Given three positive prime numbers $m_1$, $m_2$, $m_3$ (the wavelengths), three nonnegative integers $x_1$, $x_2$, $x_3$ (the measurements), and three nonnegative integers $y_1$, $y_2$, $y_3$ (the accuracies), find the smallest nonnegative integer $z$ (the smallest possible distance) such that $z$ is within distance $y_ i$ from $x_ i$ modulo $m_ i$ for each $i = 1,2,3$. An integer $x’$ is within distance$y$ from $x$ modulo $m$ if there is some integer $t$ such that $x \equiv x’ + t \pmod{m}$ and $|t| \leq y$.

-----Input-----
There are three lines of input. The first line is $m_1$ $m_2$ $m_3$, the second is $x_1$ $x_2$ $x_3$ and the third is $y_1$ $y_2$ $y_3$. You may assume that $0 < m_ i \leq 10^6$, $0 \leq x_ i < m_ i$, and $0 \leq y_ i \leq 300$ for each $i$. The numbers $m_1$, $m_2$, $m_3$ are all primes and distinct.

-----Output-----
Print one line with the answer $z$. Note that the answer might not fit in a 32-bit integer.

-----Examples-----
Sample Input:
11 13 17
5 2 4
0 0 0
Sample Output:
2095

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two integers $n$ and $\textbf{r}$. In how many ways can $\textbf{r}$ items be chosen from $n$ items?

Input Format

The first line contains the number of test cases $\mathbf{T}$. Each of the next $\mathbf{T}$ lines contains two integers $n$ and $\textbf{r}$.

Constraints

$1\leq T\leq10^5$ 

$1\leq n\leq10^9$ 

$0\leq r\leq n$

Output Format

Output $\mathbf{T}$ lines, containing the required answer for the corresponding test case. Output all answers modulo $142857$.

Sample Input
4
2 1
4 0
5 2
10 3

Sample Output
2
1
10
120

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You and your friends are in New York and are planning to go see a broadway musical. Unfortunately, New York being New York, the tickets are just a tiny bit expensive. But one of the shows has a ticket lottery each night where impecunious people such as yourself have a chance to win the right to buy slightly less expensive tickets to good seats. 

The lottery operates as follows. First, everyone interested enters the lottery. Then, $n$ lucky winners are drawn, and each of these is offered to buy up to $t$ tickets.

Given the number of people $p$ in your group (all of which entered the lottery) and the total number of people $m$ that entered the lottery, what is the probability that you will be able to get tickets for your entire group? Assume that the $n$ lucky winners are chosen uniformly at random from the $m$ people that entered the lottery, and that each person can win at most once.

-----Input-----
The input consists of a single line containing four integers:
 - $1 \le m \le 1000$: the total number of people who entered the lottery.
 - $1 \le n \le m$: the total number of winners drawn.
 - $1 \le t \le 100$: the number of tickets each winner is allowed to buy.
 - $1 \le p \le m$: the number of people in your group.

-----Output-----
Output a single line containing the probability that your entire group can get tickets to the show. This probability should be given with an absolute error of at most $10^{-9}$.

-----Examples-----
Sample Input 1:
100 10 2 1
Sample Output 1:
0.1

Sample Input 2:
100 10 2 2
Sample Output 2:
0.1909090909

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasily the bear has got a sequence of positive integers a_1, a_2, ..., a_{n}. Vasily the Bear wants to write out several numbers on a piece of paper so that the beauty of the numbers he wrote out was maximum. 

The beauty of the written out numbers b_1, b_2, ..., b_{k} is such maximum non-negative integer v, that number b_1 and b_2 and ... and b_{k} is divisible by number 2^{v} without a remainder. If such number v doesn't exist (that is, for any non-negative integer v, number b_1 and b_2 and ... and b_{k} is divisible by 2^{v} without a remainder), the beauty of the written out numbers equals -1. 

Tell the bear which numbers he should write out so that the beauty of the written out numbers is maximum. If there are multiple ways to write out the numbers, you need to choose the one where the bear writes out as many numbers as possible.

Here expression x and y means applying the bitwise AND operation to numbers x and y. In programming languages C++ and Java this operation is represented by "&", in Pascal — by "and".


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5). The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_1 < a_2 < ... < a_{n} ≤ 10^9).


-----Output-----

In the first line print a single integer k (k > 0), showing how many numbers to write out. In the second line print k integers b_1, b_2, ..., b_{k} — the numbers to write out. You are allowed to print numbers b_1, b_2, ..., b_{k} in any order, but all of them must be distinct. If there are multiple ways to write out the numbers, choose the one with the maximum number of numbers to write out. If there still are multiple ways, you are allowed to print any of them.


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

Output
2
4 5

Input
3
1 2 4

Output
1
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are 32 letters in the Polish alphabet: 9 vowels and 23 consonants. 
 
Your task is to change the letters with diacritics:

```
ą -> a,
ć -> c,
ę -> e,
ł -> l,
ń -> n,
ó -> o,
ś -> s,
ź -> z,
ż -> z
```
and print out the string without the use of the Polish letters.


For example:
```
"Jędrzej Błądziński"  -->  "Jedrzej Bladzinski"
```

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 $n$ lowercase Latin letters. Polycarp wants to remove exactly $k$ characters ($k \le n$) from the string $s$. Polycarp uses the following algorithm $k$ times:

  if there is at least one letter 'a', remove the leftmost occurrence and stop the algorithm, otherwise go to next item;  if there is at least one letter 'b', remove the leftmost occurrence and stop the algorithm, otherwise go to next item;  ...  remove the leftmost occurrence of the letter 'z' and stop the algorithm. 

This algorithm removes a single letter from the string. Polycarp performs this algorithm exactly $k$ times, thus removing exactly $k$ characters.

Help Polycarp find the resulting string.


-----Input-----

The first line of input contains two integers $n$ and $k$ ($1 \le k \le n \le 4 \cdot 10^5$) — the length of the string and the number of letters Polycarp will remove.

The second line contains the string $s$ consisting of $n$ lowercase Latin letters.


-----Output-----

Print the string that will be obtained from $s$ after Polycarp removes exactly $k$ letters using the above algorithm $k$ times.

If the resulting string is empty, print nothing. It is allowed to print nothing or an empty line (line break).


-----Examples-----
Input
15 3
cccaabababaccbc

Output
cccbbabaccbc

Input
15 9
cccaabababaccbc

Output
cccccc

Input
1 1
u

Output

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A string is said to be "SUPER STRING" if the number of times the character appeared in the string is equal to its ASCII value. Given the conditions that the ASCII value of ‘a’ is 26 and z is ‘1’.

Input 

First line takes number of test cases ‘N’.
Following ‘N’ lines take string as input.

Output

‘Yes’ if the string is a super String
‘No’ if string is not a Super String

SAMPLE INPUT
2
ZYY
ZYYZ

SAMPLE OUTPUT
Yes
No

Explanation

'Z' appeared once and 'Y' appeared twice in the first test case so it was a 'Yes' and in second test case 'Z' appeared twice therefore it was a 'No'

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer S represented as a string, the task is to get the sum of all possible sub-strings of this string.
As the answer will be large, print it modulo 10^9+7.
Example 1:
Input:
S = 1234
Output: 1670
Explanation: Sum = 1 + 2 + 3 + 4 + 12 +
23 + 34 + 123 + 234 + 1234 = 1670
Example 2:
Input:
S = 421
Output: 491
Explanation: Sum = 4 + 2 + 1 + 42 + 21
Your Task:
You only need to complete the function sumSubstrings that takes S as an argument and returns the answer modulo 1000000007.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= |S| <= 10^{4}

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