vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Chef has a binary string S of length N. 

In one operation, Chef can:
Select two indices i and j (1 ≤ i, j ≤ N, i \ne j) and flip S_{i} and S_{j}. (i.e. change 0 to 1 and 1 to 0)

For example, if S = 10010 and chef applys operation on i = 1 and j = 3 then: \underline{1}0\underline{0}10 \rightarrow 00110.

Find if it is possible to convert S to a palindrome by applying the above operation any (possibly zero) number of times.

Note: A string is called a palindrome if it reads the same backwards and forwards, for e.g. 10001 and 0110 are palindromic strings.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the length of the binary string S.
- The second line of each test case contains a binary string S of length N containing 0s and 1s only.

------ Output Format ------ 

For each test case, output YES if it is possible to convert S to a palindrome. Otherwise, output NO.

You can print each character of the string in uppercase or lowercase. For example, the strings YES, yes, Yes, and yEs are all considered the same.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$S$ contains $0$ and $1$ only.
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
6
101011
2
01
7
1110000

----- Sample Output 1 ------ 
YES
NO
YES

----- explanation 1 ------ 
Test case 1: We can perform the following operation: 
- Select $i = 3$ and $j = 5$. Then $10\underline{1}0\underline{1}1 \rightarrow 100001$, which is a palindrome.

Test case 2: It can be proven that we can not make $S$ a palindrome using the given operation.

Test case 3: We can perform the following operations: 
- Select $i = 4$ and $j = 5$. Then $111\underline{0}\underline{0}00 \rightarrow 1111100$
- Select $i = 6$ and $j = 7$. Then $11111\underline{0}\underline{0} \rightarrow 1111111$, which is a palindrome.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N people. The name of the i-th person is S_i.
We would like to choose three people so that the following conditions are met:
 - The name of every chosen person begins with M, A, R, C or H.
 - There are no multiple people whose names begin with the same letter.
How many such ways are there to choose three people, disregarding order?
Note that the answer may not fit into a 32-bit integer type.

-----Constraints-----
 - 1 \leq N \leq 10^5
 - S_i consists of uppercase English letters.
 - 1 \leq |S_i| \leq 10
 - S_i \neq S_j (i \neq j)

-----Input-----
Input is given from Standard Input in the following format:
N
S_1
:
S_N

-----Output-----
If there are x ways to choose three people so that the given conditions are met, print x.

-----Sample Input-----
5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI

-----Sample Output-----
2

We can choose three people with the following names:
 - MASHIKE, RUMOI, HABORO
 - MASHIKE, RUMOI, HOROKANAI
Thus, we have two ways.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Amidakuji is a traditional method of lottery in Japan.
To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1 [cm], and the endpoints of the horizontal lines must be at 1, 2, 3, ..., or H [cm] from the top of a vertical line.
A valid amidakuji is an amidakuji that satisfies the following conditions:
 - No two horizontal lines share an endpoint.
 - The two endpoints of each horizontal lines must be at the same height.
 - A horizontal line must connect adjacent vertical lines.

Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.
For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.

-----Constraints-----
 - H is an integer between 1 and 100 (inclusive).
 - W is an integer between 1 and 8 (inclusive).
 - K is an integer between 1 and W (inclusive).

-----Input-----
Input is given from Standard Input in the following format:
H W K

-----Output-----
Print the number of the amidakuji that satisfy the condition, modulo 1\ 000\ 000\ 007.

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

-----Sample Output-----
1

Only the following one amidakuji satisfies the condition:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The famous Jurassic park biologist Dean O’Saur has discovered new samples of what he expects to be the DNA of a dinosaur. With the help of his assistant Petra Dactil, he managed to sequence the samples, and now they are ready for analysis. Dean thinks this dinosaur was affected with a particular disease that mutated the DNA of some cells.

To verify his theory, he needs to compute the most likely evolutionary tree from the samples, where the nodes are the samples of DNA. Because there is no temporal data for the DNA samples, he is not concerned where the root of the tree is.

Dean considers the most likely evolutionary tree, the tree with smallest unlikeliness: the unlikeliness of a tree is defined as the sum of the weights of all edges, where the weight of an edge is the number of positions at which the two DNA strings are different.

As a world expert in data trees, he asks you to reconstruct the most likely evolutionary tree.

In the first sample, the optimal tree is AA - AT - TT - TC . The unlikeliness of the edge between AA and AT edge is $1$, because the strings AA and AT differ in exactly $1$ position. The weights of the other two edges are also $1$, so that the unlikeliness of the entire tree is $3$. Since there is no tree of unlikeliness less than $3$, the minimal unlikeliness of an evolutionary tree for this case is $3$.

-----Input-----
 - The first line consists of two integers $1\leq n\leq 1000$ and $1\leq k\leq 10$, the number of samples and the length of each sample respectively.
 - Each of the next $n$ lines contains a string of length $k$ consisting of the characters in ACTG.

-----Output-----
 - On the first line, print the minimal unlikeliness of the evolutionary tree.
 - Then, print $n-1$ lines, each consisting of two integers $0\leq u,v < n$, indicating that in the most likely evolutionary tree, there is an edge between DNA string $u$ and $v$. If there are multiple answers possible, any of them will be accepted.

-----Examples-----
Sample Input 1:
4 2
AA
AT
TT
TC
Sample Output 1:
3
0 1
1 2
2 3

Sample Input 2:
4 1
A
A
G
T
Sample Output 2:
2
0 1
0 2
0 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ Christmas trees on an infinite number line. The $i$-th tree grows at the position $x_i$. All $x_i$ are guaranteed to be distinct.

Each integer point can be either occupied by the Christmas tree, by the human or not occupied at all. Non-integer points cannot be occupied by anything.

There are $m$ people who want to celebrate Christmas. Let $y_1, y_2, \dots, y_m$ be the positions of people (note that all values $x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$ should be distinct and all $y_j$ should be integer). You want to find such an arrangement of people that the value $\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|$ is the minimum possible (in other words, the sum of distances to the nearest Christmas tree for all people should be minimized).

In other words, let $d_j$ be the distance from the $j$-th human to the nearest Christmas tree ($d_j = \min\limits_{i=1}^{n} |y_j - x_i|$). Then you need to choose such positions $y_1, y_2, \dots, y_m$ that $\sum\limits_{j=1}^{m} d_j$ is the minimum possible.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of Christmas trees and the number of people.

The second line of the input contains $n$ integers $x_1, x_2, \dots, x_n$ ($-10^9 \le x_i \le 10^9$), where $x_i$ is the position of the $i$-th Christmas tree. It is guaranteed that all $x_i$ are distinct.


-----Output-----

In the first line print one integer $res$ — the minimum possible value of $\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|$ (in other words, the sum of distances to the nearest Christmas tree for all people).

In the second line print $m$ integers $y_1, y_2, \dots, y_m$ ($-2 \cdot 10^9 \le y_j \le 2 \cdot 10^9$), where $y_j$ is the position of the $j$-th human. All $y_j$ should be distinct and all values $x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$ should be distinct.

If there are multiple answers, print any of them.


-----Examples-----
Input
2 6
1 5

Output
8
-1 2 6 4 0 3 

Input
3 5
0 3 1

Output
7
5 -2 4 -1 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A mysterious circular arrangement of black stones and white stones has appeared. Ming has been tasked with balancing the stones so that only one black and one white stone remain.

Ming has two operations for balancing the stones:
 - Take some consecutive sequence of stones where there is exactly one more black stone than a white stone and replace the stones with a single black stone
 - Take some consecutive sequence of stones where there is exactly one more white stone than black stone and replace the stones with a single white stone

Given a circular arrangement, determine if it is possible for Ming to balance the stones.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The input will consist of a single string $s$ ($1 \le |s| \le 10^5$), with only the characters capital ‘B’ and ‘W’. The stones are arranged in a circle, so the first stone and the last stone are adjacent.

-----Output-----
Output $1$ if it is possible for Ming to balance the stones with his rules. Otherwise, output $0$.

-----Examples-----
Sample Input 1:
WWBWBB
Sample Output 1:
1

Sample Input 2:
WWWWBBW
Sample Output 2:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nowadays, there are a lot of unusual people. We won’t go into details, but instead focus on a certain type, to us personally the most interesting people. Of course, we’re talking about barbarians!

There are a lot of barbarians, but only a few of them are truly important. This story has $N$ important barbarians, denoted with integers from $1$ to $N$. Each of them has their own stone tablet with their word written on it, consisting of only lowercase letters of the English alphabet.

Our barbarians are playing an interesting game with their good friend Tarzan.

The game is played in $Q$ rounds. There are two round types and each is determined by Tarzan:1st type:

Tarzan shows the word $P$ to the barbarians.2nd type:

Tarzan asks the barbarian denoted with $S$ the following question: “Out of all the words I’ve shown you so far, how many of them have the word on your stone tablet as a consecutive substring?”

Given the fact that the barbarians go wild a lot and aren’t really able to pay attention and keep up with what’s happening in the game, they need your help. Help the barbarians answer each of Tarzan’s questions correctly.

-----Input-----
The first line of input contains the integer $N$ ($1 \leq N \leq 10^5$), the number of barbarians.

Each of the following $N$ lines contains a single word consisting of only lowercase letters of the English alphabet, the $i$-th word corresponding to the word on the stone tablet of barbarian denoted with $i$.

After that, the integer $Q$ ($1 \leq Q \leq 10^5$) follows, the number of rounds in the game.

The following $Q$ lines describe the round of the game, the $i$-th line describing the $i$-th round of the game. Each line will contain the integer $T$. In the case when $T$ is equal to 1, it denotes the first type of round and the shown word $P$ follows in the same line, consisting of only lowercase letters of the English alphabet.

In the case when $T$ is equal to 2, it denotes the second type of round and the number $S$ ($1 \leq S \leq N$) follows in the same line, the label of the barbarian whom Tarzan asked the question.

The total length of all words written on the barbarians’ stone tablets will not exceed $2 \cdot 10^6$.

The total length of all words that Tarzan shows the barbarians will not exceed $2 \cdot 10^6$.

-----Output-----
For each round of the second form, output a single line. The $i$-th line must contain the correct answer to Tarzan’s question in the $i$-th round of type 2.

-----Examples-----
Sample Input:
3
a
bc
abc
3
1 abca
2 1
2 3
Sample Output:
1
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Housing maker Yamada House has launched a new featured product, a land for sale in a green home town with a rich environment such as schools and hospitals. This lot is divided into multiple lots and you can buy as many as you like, but the shape of the land with the lots you buy must be rectangular (including squares).

Yamada House has drawn a boundary for each purchaser in order to manage the lots sold out in all lots, and installed a sign with the purchaser number on one of the lots. The border was just a line drawn on the ground with tree branches, so it disappeared due to heavy rain a few days later, leaving only the sign. Figure 1 shows the number of the purchaser who bought the section on the section with the sign. This doesn't tell you how the land for sale was bought. The salvation is that I found a note (Figure 2) with the purchaser number b and the number of parcels k purchased in the office drawer.


<image>


Fig. 1 (left): Arrangement of signboards, Fig. 2 (right): Memo

As a programmer, you decided to write a program to help Yamada House. Create a program that inputs the size of the lot for sale X × Y, the number of purchasers n, the memo information b, k, and the location information s of the signboard, and outputs the purchasers of each section as shown in Fig. 3. Please give me.


<image>


Figure 3: Buyers of each parcel

For the given information, NA is output in the following cases.

* If there is no way to distinguish the parcels
* When there are multiple ways to distinguish between parcels



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by three lines of zeros. Each dataset is given in the following format:


X Y n
b1 k1
b2 k2
::
bn kn
s11 s21 ... sX1
s12 s22 ... sX2
::
s1Y s2Y ... sXY


The first line gives X, Y, n (1 ≤ X, Y ≤ 10, 1 ≤ n ≤ 15). The following n lines give the information bi (1 ≤ bi ≤ n), ki (1 ≤ ki ≤ 100) written on the i line of the memo.

The following Y line is given the information sij on the i-th line of the partition information. sij represents the sign information of the jth section from the left on the i-th line. Sign information sij is given 0 if there is no sign in the parcel, and the purchaser number of the parcel if there is a sign.

The number of datasets does not exceed 50.

Output

Prints buyer information or NA for each input dataset.

Example

Input

5 4 6
1 6
2 4
3 3
4 4
5 1
6 2
0 0 1 0 0
0 0 0 2 0
0 0 0 3 0
0 4 5 0 6
3 3 1
1 9
0 0 1
0 0 0
0 0 0
4 4 4
1 6
2 2
3 4
4 4
0 1 0 0
0 0 0 2
0 0 3 0
0 4 0 0
0 0 0


Output

1 1 1 2 2
1 1 1 2 2
4 4 3 3 3
4 4 5 6 6
1 1 1
1 1 1
1 1 1
NA

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke has an integer sequence A of length N.
He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B, C, D and E.
The positions of the cuts can be freely chosen.
Let P,Q,R,S be the sums of the elements in B,C,D,E, respectively.
Snuke is happier when the absolute difference of the maximum and the minimum among P,Q,R,S is smaller.
Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

-----Constraints-----
 - 4 \leq N \leq 2 \times 10^5
 - 1 \leq A_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

-----Sample Input-----
5
3 2 4 1 2

-----Sample Output-----
2

If we divide A as B,C,D,E=(3),(2),(4),(1,2), then P=3,Q=2,R=4,S=1+2=3.
Here, the maximum and the minimum among P,Q,R,S are 4 and 2, with the absolute difference of 2.
We cannot make the absolute difference of the maximum and the minimum less than 2, so the answer is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We are well known with the two personalities Gabbar Singh & Phoolan Devi. Gabbar Singh , the most iconic villain of Hindi Film Industry whereas Phoolan Devi ,  the Bandit Queen.

Now the battle is in between these two for expanding their territory. The dual came face to face for fighting for their territory. 

But this time its not the Battle with guns or grenade , instead they both chosen a peaceful method for solving their hunger for territory.

A race was held between them ,  and the one who reach exactly on the Finishing Line first will win. If the both reach exactly on the Finishing Line at same time its a Tie. And for any other condition the race will be counted as Invalid.

Now during the race they both speed up and slow down frequently. Each time any of them Speed Up it increase their s[peed by one unit. And for Slowing Down condition it will decrease the Speed with a factor of one unit.

At start their position are at zero and their speed is also equal to zero

Find out the result of race

Input : First line will contain an integer T number of Test Cases. Each test case will contain the following inputs . First line of each test case will tell the integer L length of Race Track. Second line of each test case will tell integer C the number of changes in their speeds . Then next C lines will have G F characters. Please see the property for character G F

if G/F => F , it means Speed Up

if G/F => B , it means Slow Down

if G/F => W , nothing

Output : Print the result. If Gabbar Singh wins then print GABBAR SINGH , if Phooaln Devi wins print PHOOLAN DEVI , if its a tie then print TIE , if race is invalid then print INVALID. For each test case print result in new line.

Format of output is Case x: y where x is test case number and y is result

Constraints

1 ≤ T ≤ 100

15 ≤ L ≤ 10^6

1 ≤ C ≤ 100

UPDATE : For the given problem both Gabbar Singh and Phoolan Devi starts with zero position. Length of track is given and race is organised. Till the completion of race speed of both are changed which can be fetched from the corresponding inputs. 'F' means increment of one in speed , 'B' means decrements of one in speed, 'W' means no change in speed. 
Now one who reached exactly on Finishing Line of track first will win. Note that , position change from current Position depends on current speed of them.

SAMPLE INPUT
2
25
6
F F
B B
W W
F F
B F
W F
15
8
F F
F W
F F
F F
B F
B B
F F
F B

SAMPLE OUTPUT
Case 1: PHOOLAN DEVI
Case 2: GABBAR SINGH

Explanation

In Case 1 : Phoolan Devi will reach first exactly on Finishing Line

In Case 2  : Gabbar Singh will reach first exactly on Finishing Line

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sorting is useful as the first step in many different tasks. The most common task is to make finding things easier, but there are other uses as well.  In this case, it will make it easier to determine which pair or pairs of elements have the smallest absolute difference between them.

Example 

$arr=[5,2,3,4,1]$   

Sorted, $ar r'=[1,2,3,4,5]$.  Several pairs have the minimum difference of $1$: $[(1,2),(2,3),(3,4),(4,5)]$.  Return the array $[1,2,2,3,3,4,4,5]$.

Note 

As shown in the example, pairs may overlap.  

Given a list of unsorted integers, $\textbf{arr}$, find the pair of elements that have the smallest absolute difference between them. If there are multiple pairs, find them all.

Function Description  

Complete the closestNumbers function in the editor below.   

closestNumbers has the following parameter(s):  

int arr[n]: an array of integers   

Returns 

- int[]: an array of integers as described   

Input Format

The first line contains a single integer $n$, the length of $\textbf{arr}$. 

The second line contains $n$ space-separated integers, $arr\left[i\right]$.

Constraints

$2\leq n\leq200000$
$-10^7\leq arr[i]\leq10^7$
All $a[i]$ are unique in $\textbf{arr}$.

Output Format

Sample Input 0

10
-20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854 

Sample Output 0

-20 30

Explanation 0 

(30) - (-20) = 50, which is the smallest difference.  

Sample Input 1

12
-20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854 -520 -470 

Sample Output 1

-520 -470 -20 30

Explanation 1 

(-470) - (-520) = 30 - (-20) = 50, which is the smallest difference. 

Sample Input 2

4
5 4 3 2

Sample Output 2

2 3 3 4 4 5

Explanation 2 

Here, the minimum difference is 1. Valid pairs are (2, 3), (3, 4), and (4, 5).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number N, find the most occurring digit in it. If two or more digits occur same number of times, then return the highest of them. Input number is given as a string.
Example 1:
Input:
N = "12234"
Output:
2
Explanation :
2 occurs most times
Example 2:
Input:
N = "1122"
Output:
2
Explanation :
1 and 2 occurs most times but 2 > 1.
 
Your Task: 
You don't need to read input or print anything. Your task is to complete the function solve() that receives a string N as input parameter and returns the most frequent digit in it as a string.
Expected Time Complexity : O(len(N))
Expected Space Complexity : O(1)
Constraints:
1<= len(N) <=101000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider an analog clock whose hour and minute hands are A and B centimeters long, respectively.

An endpoint of the hour hand and an endpoint of the minute hand are fixed at the same point, around which each hand rotates clockwise at constant angular velocity. It takes the hour and minute hands 12 hours and 1 hour to make one full rotation, respectively.

At 0 o'clock, the two hands overlap each other. H hours and M minutes later, what is the distance in centimeters between the unfixed endpoints of the hands?

Constraints

* All values in input are integers.
* 1 \leq A, B \leq 1000
* 0 \leq H \leq 11
* 0 \leq M \leq 59

Input

Input is given from Standard Input in the following format:


A B H M


Output

Print the answer without units. Your output will be accepted when its absolute or relative error from the correct value is at most 10^{-9}.

Examples

Input

3 4 9 0


Output

5.00000000000000000000


Input

3 4 10 40


Output

4.56425719433005567605

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