vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Uppal-balu is busy in extraction of gold from ores. He got an assignment from his favorite professor MH sir, but he got stuck in a problem. Can you help Uppal-balu to solve the problem.
You are given an array $a_1$, $a_2$, $\dots$, $a_n$ of length $n$. You can perform the following operations on it:
- Choose an index $i$ ($1 \leq i \leq n$), and replace $a_i$ by $a_{i} + 1$ or $a_{i} - 1$, which means add or subtract one to the element at index $i$.
Beauty of the array is defined as maximum length of a subarray containing numbers which give same remainder upon dividing it by $k$ (that is, ($a_l$ mod $k$) = ($a_{l+1}$ mod $k$) = $\dots$ = ($a_r$ mod $k$) for some $1 \leq l \leq r \leq n$).
You need to calculate the beauty of the array $a_1$, $a_2$, $\dots$, $a_n$ after applying at most $m$ operations.
NOTE:
- The subarray of a is a contiguous part of the array $a$, i. e. the array $a_l$, $a_{l+1}$, $\dots$, $a_r$ for some $1 \leq l \leq r \leq n$.
- $x$ mod $y$ means the remainder of $x$ after dividing it by $y$.

-----Input:-----
- First line of input contains 3 integers $n$, $m$ and $k$.   
- The second line contains $n$ integers $a_1$, $a_2$, $\dots$, $a_n$.

-----Output:-----
Output in a single line the beauty of the array after applying at most m operations.

-----Constraints-----
- $1 \leq n,m \leq 2\cdot10^{5}$
- $1 \leq k \leq 7$
- $1 \leq a_i \leq 10^9$

-----Sample Input 1:-----
7 3 4

8 2 3 7 8 1 1    

-----Sample Output 1:-----
5

-----Sample Input 2:-----
8 3 5

7 2 1 3 6 5 6 2   

-----Sample Output 2:-----
5

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Maxim loves to fill in a matrix in a special manner. Here is a pseudocode of filling in a matrix of size (*m*<=+<=1)<=×<=(*m*<=+<=1):



Maxim asks you to count, how many numbers *m* (1<=≤<=*m*<=≤<=*n*) are there, such that the sum of values in the cells in the row number *m*<=+<=1 of the resulting matrix equals *t*.

Expression (*x* *xor* *y*) means applying the operation of bitwise excluding "OR" to numbers *x* and *y*. The given operation exists in all modern programming languages. For example, in languages C++ and Java it is represented by character "^", in Pascal — by "xor".

Input Specification:
A single line contains two integers *n* and *t* (1<=≤<=*n*,<=*t*<=≤<=1012,<=*t*<=≤<=*n*<=+<=1).

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output Specification:
In a single line print a single integer — the answer to the problem.

Demo Input:
['1 1\n', '3 2\n', '3 3\n', '1000000000000 1048576\n']

Demo Output:
['1\n', '1\n', '0\n', '118606527258\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hooray! Polycarp turned $n$ years old! The Technocup Team sincerely congratulates Polycarp!

Polycarp celebrated all of his $n$ birthdays: from the $1$-th to the $n$-th. At the moment, he is wondering: how many times he turned beautiful number of years?

According to Polycarp, a positive integer is beautiful if it consists of only one digit repeated one or more times. For example, the following numbers are beautiful: $1$, $77$, $777$, $44$ and $999999$. The following numbers are not beautiful: $12$, $11110$, $6969$ and $987654321$.

Of course, Polycarpus uses the decimal numeral system (i.e. radix is 10).

Help Polycarpus to find the number of numbers from $1$ to $n$ (inclusive) that are beautiful.


-----Input-----

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

Each test case consists of one line, which contains a positive integer $n$ ($1 \le n \le 10^9$) — how many years Polycarp has turned.


-----Output-----

Print $t$ integers — the answers to the given test cases in the order they are written in the test. Each answer is an integer: the number of beautiful years between $1$ and $n$, inclusive.


-----Example-----
Input
6
18
1
9
100500
33
1000000000

Output
10
1
9
45
12
81



-----Note-----

In the first test case of the example beautiful years are $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$ and $11$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Programmers Army Land, people have started preparation as sports day is scheduled next week.
You are given a task to form 1 team of $k$ consecutive players, from a list of sports player whose powers are given to you.
You want your team to win this championship, so you have to chose your $k$ team players optimally i.e. there must not be any other $k$ consecutive team players who have their total power greater than your team members total power.

-----Input:-----
- The first line of the input contains a single integer $T$. $T$ denoting the number of test cases. The description of $T$ test cases is as follows.
- The next line of the input contains 2 space separated integers $N$ and $K$. $N$ denotes the total number of players and $K$ denotes the number of players allowed in a team.
- The next line of the input contains $N$ space-separated integers $A1, A2, A3...An$ where $ith$ number denotes power of $ith$ player.
Note: power of players can also be negative

-----Output:-----
- For each test-case print the total power that your selected team have(each test case output must be printed on a new line).

-----Constraints:-----
- $1 \leq T \leq 10^3$
- $1 \leq N,K \leq 10^5$
- $-10^7 \leq A1, A2, A3...An \leq 10^7$

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

-----Sample Output:-----
12

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day Kefa found *n* baloons. For convenience, we denote color of *i*-th baloon as *s**i* — lowercase letter of the Latin alphabet. Also Kefa has *k* friends. Friend will be upset, If he get two baloons of the same color. Kefa want to give out all baloons to his friends. Help Kefa to find out, can he give out all his baloons, such that no one of his friens will be upset — print «YES», if he can, and «NO», otherwise. Note, that Kefa's friend will not upset, if he doesn't get baloons at all.

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*n*,<=*k*<=≤<=100) — the number of baloons and friends.

Next line contains string *s* — colors of baloons.

Output Specification:
Answer to the task — «YES» or «NO» in a single line.

You can choose the case (lower or upper) for each letter arbitrary.

Demo Input:
['4 2\naabb\n', '6 3\naacaab\n']

Demo Output:
['YES\n', 'NO\n']

Note:
In the first sample Kefa can give 1-st and 3-rd baloon to the first friend, and 2-nd and 4-th to the second.

In the second sample Kefa needs to give to all his friends baloons of color a, but one baloon will stay, thats why answer is «NO».

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Suppose we abstract our file system by a string in the following manner:

The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:

dir
    subdir1
    subdir2
        file.ext


The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents:

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext


The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.

We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is "dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes).

Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return 0.

Note:

The name of a file contains at least a . and an extension.
The name of a directory or sub-directory will not contain a ..



Time complexity required: O(n) where n is the size of the input string.

Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Max feels lonely after shifting to a new locality, as he does not have any friend there. So his parents bought him a new number from the Integers SuperMarket! Every child in the locality has bought a number from the same market.  

He takes the number to go play with other children in the locality. But to his surprise, there is a rule in the locality, two people A and B can only be considered friends if numbers with A and B are not Coprime, i.e they have a common factor other than 1.  

You are given the number that Max bought and the numbers of other children in the locality. Can you find how many friends he can have?   

Input:
First line contains an integer A, the number that Max has.
Second line contains N, the count of children in the locality.
Third line contains N space-separated integers, where  Xi is the integer with the i^th child.  

Output:
Output the maximum number of friends that Max can make.  

Constraints:
1 ≤ A ≤ 10^3
1 ≤ N ≤ 10^3
1 ≤ Xi  ≤ 10^3

SAMPLE INPUT
6
3
4 7 12

SAMPLE OUTPUT
2

Explanation

Puchi can become friends with First and Third child.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.


Example 1:

Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.



Example 2:

Input: 9973
Output: 9973
Explanation: No swap.




Note:

The given number is in the range [0, 108]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given four integers A, B, C, and D. Find the number of integers between A and B (inclusive) that can be evenly divided by neither C nor D.

-----Constraints-----
 - 1\leq A\leq B\leq 10^{18}
 - 1\leq C,D\leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
A B C D

-----Output-----
Print the number of integers between A and B (inclusive) that can be evenly divided by neither C nor D.

-----Sample Input-----
4 9 2 3

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

5 and 7 satisfy the condition.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a binary string S of N bits. The bits in the string are indexed starting from 1. S[i] denotes the ith bit of S.

Let's say that a sequence i1, i2, …, iK(1 ≤ K; 1 ≤ i1 < i2 < … < iK ≤ N) produces a palindrome when applied to S, if the string S[i1] S[i2] … S[ik] is a palindrome (that is, reads the same backward or forward).

In addition, a sequence i1, i2, …, iK(1 ≤ K; 1 ≤ i1 < i2 < … < iK ≤ N) is said to be exponential, if ij + 1 = p * ij for each integer 1 ≤ j < K and for some integer p > 1. Note, that a sequence of one element is always exponential.

Your task is to count the number of exponential sequences that produce a palindrome when applied to S.

-----Input-----
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.

The only line of description for each test case contains a binary string S of N bits.

-----Output-----

For each test case, output a single line containing the number of exponential sequences that produce a palindrome.

-----Constraints-----
- 1 ≤ T ≤ 10
- Subtask 1(20 points): 1 ≤ N ≤ 20
- Subtask 2(30 points): 1 ≤ N ≤ 1000
- Subtask 3(50 points): 1 ≤ N ≤ 5 × 105

-----Note-----

The first test of the first subtask is the example test. It's made for you to make sure that your solution produces the same verdict both on your machine and our server.

-----Time Limits-----

Time limit for the first and the second subtasks is 3s. Time limit for the third subtask is 6s.

-----Example-----
Input:
2
11010
101001011

Output:
9
18

-----Explanation of the first case in the example test-----

The following sequences are counted in the answer: {1}, {2}, {3}, {4}, {5}, {1, 2}, {1, 4}, {2, 4}, {1, 2, 4}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the world of birding there are four-letter codes for the common names of birds. These codes are created by some simple rules:

* If the bird's name has only one word, the code takes the first four letters of that word. 
* If the name is made up of two words, the code takes the first two letters of each word.
* If the name is made up of three words, the code is created by taking the first letter from the first two words and the first two letters from the third word.
* If the name is four words long, the code uses the first letter from all the words.

*(There are other ways that codes are created, but this Kata will only use the four rules listed above)*

Complete the function that takes an array of strings of common bird names from North America, and create the codes for those names based on the rules above. The function should return an array of the codes in the same order in which the input names were presented.

Additional considertations:

* The four-letter codes  in the returned array should be in UPPER CASE.
* If a common name has a hyphen/dash, it should be considered a space. 

## Example

If the input array is: `["Black-Capped Chickadee", "Common Tern"]`

The return array would be: `["BCCH", "COTE"]`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two positive integers N and K. How many multisets of rational numbers satisfy all of the following conditions?
 - The multiset has exactly N elements and the sum of them is equal to K.
 - Each element of the multiset is one of 1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \dots. In other words, each element can be represented as \frac{1}{2^i}\ (i = 0,1,\dots).
The answer may be large, so print it modulo 998244353.

-----Constraints-----
 - 1 \leq K \leq N \leq 3000
 - All values in input are integers.

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

-----Output-----
Print the number of multisets of rational numbers that satisfy all of the given conditions modulo 998244353.

-----Sample Input-----
4 2

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

The following two multisets satisfy all of the given conditions:
 - {1, \frac{1}{2}, \frac{1}{4}, \frac{1}{4}}
 - {\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a square grid of size $n \times n$. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs $\min(h, w)$ to color a rectangle of size $h \times w$. You are to make all cells white for minimum total cost.

The square is large, so we give it to you in a compressed way. The set of black cells is the union of $m$ rectangles.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^{9}$, $0 \le m \le 50$) — the size of the square grid and the number of black rectangles.

Each of the next $m$ lines contains 4 integers $x_{i1}$ $y_{i1}$ $x_{i2}$ $y_{i2}$ ($1 \le x_{i1} \le x_{i2} \le n$, $1 \le y_{i1} \le y_{i2} \le n$) — the coordinates of the bottom-left and the top-right corner cells of the $i$-th black rectangle.

The rectangles may intersect.


-----Output-----

Print a single integer — the minimum total cost of painting the whole square in white.


-----Examples-----
Input
10 2
4 1 5 10
1 4 10 5

Output
4

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

Output
3



-----Note-----

The examples and some of optimal solutions are shown on the pictures below.

 [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The New Vasjuki village is stretched along the motorway and that's why every house on it is characterized by its shift relative to some fixed point — the xi coordinate. The village consists of n houses, the i-th house is located in the point with coordinates of xi.

TELE3, a cellular communication provider planned to locate three base stations so as to provide every house in the village with cellular communication. The base station having power d located in the point t provides with communication all the houses on the segment [t - d, t + d] (including boundaries).

To simplify the integration (and simply not to mix anything up) all the three stations are planned to possess the equal power of d. Which minimal value of d is enough to provide all the houses in the village with cellular communication.

Input

The first line contains an integer n (1 ≤ n ≤ 2·105) which represents the number of houses in the village. The second line contains the coordinates of houses — the sequence x1, x2, ..., xn of integer numbers (1 ≤ xi ≤ 109). It is possible that two or more houses are located on one point. The coordinates are given in a arbitrary order.

Output

Print the required minimal power d. In the second line print three numbers — the possible coordinates of the base stations' location. Print the coordinates with 6 digits after the decimal point. The positions of the stations can be any from 0 to 2·109 inclusively. It is accepted for the base stations to have matching coordinates. If there are many solutions, print any of them.

Examples

Input

4
1 2 3 4


Output

0.500000
1.500000 2.500000 3.500000


Input

3
10 20 30


Output

0
10.000000 20.000000 30.000000


Input

5
10003 10004 10001 10002 1


Output

0.500000
1.000000 10001.500000 10003.500000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A Christmas party in city S. had n children. All children came in mittens. The mittens can be of different colors, but each child had the left and the right mitten of the same color. Let's say that the colors of the mittens are numbered with integers from 1 to m, and the children are numbered from 1 to n. Then the i-th child has both mittens of color c_{i}.

The Party had Santa Claus ('Father Frost' in Russian), his granddaughter Snow Girl, the children danced around the richly decorated Christmas tree. In fact, everything was so bright and diverse that the children wanted to wear mittens of distinct colors. The children decided to swap the mittens so that each of them got one left and one right mitten in the end, and these two mittens were of distinct colors. All mittens are of the same size and fit all the children.

The children started exchanging the mittens haphazardly, but they couldn't reach the situation when each child has a pair of mittens of distinct colors. Vasily Petrov, the dad of one of the children, noted that in the general case the children's idea may turn out impossible. Besides, he is a mathematician and he came up with such scheme of distributing mittens that the number of children that have distinct-colored mittens was maximum. You task is to repeat his discovery. Note that the left and right mittens are different: each child must end up with one left and one right mitten.


-----Input-----

The first line contains two integers n and m — the number of the children and the number of possible mitten colors (1 ≤ n ≤ 5000, 1 ≤ m ≤ 100). The second line contains n integers c_1, c_2, ... c_{n}, where c_{i} is the color of the mittens of the i-th child (1 ≤ c_{i} ≤ m).


-----Output-----

In the first line, print the maximum number of children who can end up with a distinct-colored pair of mittens. In the next n lines print the way the mittens can be distributed in this case. On the i-th of these lines print two space-separated integers: the color of the left and the color of the right mitten the i-th child will get. If there are multiple solutions, you can print any of them.


-----Examples-----
Input
6 3
1 3 2 2 1 1

Output
6
2 1
1 2
2 1
1 3
1 2
3 1

Input
4 2
1 2 1 1

Output
2
1 2
1 1
2 1
1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After you had helped Fedor to find friends in the «Call of Soldiers 3» game, he stopped studying completely. Today, the English teacher told him to prepare an essay. Fedor didn't want to prepare the essay, so he asked Alex for help. Alex came to help and wrote the essay for Fedor. But Fedor didn't like the essay at all. Now Fedor is going to change the essay using the synonym dictionary of the English language.

Fedor does not want to change the meaning of the essay. So the only change he would do: change a word from essay to one of its synonyms, basing on a replacement rule from the dictionary. Fedor may perform this operation any number of times.

As a result, Fedor wants to get an essay which contains as little letters «R» (the case doesn't matter) as possible. If there are multiple essays with minimum number of «R»s he wants to get the one with minimum length (length of essay is the sum of the lengths of all the words in it). Help Fedor get the required essay.

Please note that in this problem the case of letters doesn't matter. For example, if the synonym dictionary says that word cat can be replaced with word DOG, then it is allowed to replace the word Cat with the word doG.


-----Input-----

The first line contains a single integer m (1 ≤ m ≤ 10^5) — the number of words in the initial essay. The second line contains words of the essay. The words are separated by a single space. It is guaranteed that the total length of the words won't exceed 10^5 characters.

The next line contains a single integer n (0 ≤ n ≤ 10^5) — the number of pairs of words in synonym dictionary. The i-th of the next n lines contains two space-separated non-empty words x_{i} and y_{i}. They mean that word x_{i} can be replaced with word y_{i} (but not vise versa). It is guaranteed that the total length of all pairs of synonyms doesn't exceed 5·10^5 characters.

All the words at input can only consist of uppercase and lowercase letters of the English alphabet.


-----Output-----

Print two integers — the minimum number of letters «R» in an optimal essay and the minimum length of an optimal essay.


-----Examples-----
Input
3
AbRb r Zz
4
xR abRb
aA xr
zz Z
xr y

Output
2 6

Input
2
RuruRu fedya
1
ruruRU fedor

Output
1 10

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