vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A daily train consists of N cars. Let's consider one particular car. It has 54 places numbered consecutively from 1 to 54, some of which are already booked and some are still free. The places are numbered in the following fashion:

The car is separated into 9 compartments of 6 places each, as shown in the picture. So, the 1st compartment consists of places 1, 2, 3, 4, 53 and 54, the 2nd compartment consists of places 5, 6, 7, 8, 51 and 52, and so on.

A group of X friends wants to buy tickets for free places, all of which are in one compartment (it's much funnier to travel together). You are given the information about free and booked places in each of the N cars. Find the number of ways to sell the friends exactly X tickets in one compartment (note that the order in which the tickets are sold doesn't matter).

-----Input-----
The first line of the input contains two integers X and N (1 ≤ X ≤ 6, 1 ≤ N ≤ 10) separated by a single space. Each of the following N lines contains the information about one car which is a string of length 54 consisting of '0' and '1'. The i-th character (numbered from 1) is '0' if place i in the corresponding car is free, and is '1' if place i is already booked.

-----Output-----
Output just one integer -- the requested number of ways.

-----Example-----
Input:
1 3
100101110000001011000001111110010011110010010111000101
001010000000101111100000000000000111101010101111111010
011110011110000001010100101110001011111010001001111010

Output:
85

Input:
6 3
100101110000001011000001111110010011110010010111000101
001010000000101111100000000000000111101010101111111010
011110011110000001010100101110001011111010001001111010

Output:
1

Input:
3 2
000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000

Output:
360

Explanation:
In the first test case, any of the free places can be sold. In the second test case, the only free compartment in the train is compartment 3 in the first car (places 9, 10, 11, 12, 49 and 50 are all free). In the third test case, the train is still absolutely free; as there are 20 ways to sell 3 tickets in an empty compartment, the answer is 2 * 9 * 20 = 360.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an unordered array of unique integers incrementing from $\mbox{1}$.  You can swap any two elements a limited number of times.  Determine the largest lexicographical value array that can be created by executing no more than the limited number of swaps.  

Example 

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

$k=1$    

The following arrays can be formed by swapping the $\mbox{I}$ with the other elements: 

[2,1,3,4]
[3,2,1,4]
[4,2,3,1]

The highest value of the four (including the original) is $[4,2,3,1]$.  If $k\geq2$, we can swap to the highest possible value: $[4,3,2,1]$.

Function Description  

Complete the largestPermutation function in the editor below.  It must return an array that represents the highest value permutation that can be formed.  

largestPermutation has the following parameter(s):  

int k: the maximum number of swaps  
int arr[n]: an array of integers  

Input Format

The first line contains two space-separated integers $n$ and $\boldsymbol{\mbox{k}}$, the length of $\textbf{arr}$ and the maximum swaps that can be performed.
The second line contains $n$ distinct space-separated integers from $\mbox{1}$ to $n$ as $arr\left[i\right]$ where $1\leq ar r[i]\leq n$.

Constraints

$1\leq n\leq10^5$ 

$1\leq k\leq10^9$  

Output Format

Print the lexicographically largest permutation you can make with at most $\boldsymbol{\mbox{k}}$ swaps. 

Sample Input 0  

STDIN       Function
-----       --------
5 1         n = 5, k = 1
4 2 3 5 1   arr = [4, 2, 3, 5, 1]

Sample Output 0  

5 2 3 4 1

Explanation 0  

You can swap any two numbers in $[4,2,3,5,1]$ and see the largest permutation is $[5,2,3,4,1]$

Sample Input 1

3 1
2 1 3

Sample Output 1  

3 1 2

Explanation 1  

With 1 swap we can get $[1,2,3]$, $[3,1,2]$ and $[2,3,1]$.  Of these, $[3,1,2]$ is the largest permutation.  

Sample Input 2

2 1
2 1

Sample Output 2  

2 1

Explanation 2  

We can see that $[2,1]$ is already the largest permutation.  We don't make any swaps.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
What-The-Fatherland is a strange country! All phone numbers there are strings consisting of lowercase English letters. What is double strange that a phone number can be associated with several bears!

In that country there is a rock band called CF consisting of n bears (including Mike) numbered from 1 to n. 

<image>

Phone number of i-th member of CF is si. May 17th is a holiday named Phone Calls day. In the last Phone Calls day, everyone called all the numbers that are substrings of his/her number (one may call some number several times). In particular, everyone called himself (that was really strange country).

Denote as call(i, j) the number of times that i-th member of CF called the j-th member of CF. 

The geek Mike has q questions that he wants to ask you. In each question he gives you numbers l, r and k and you should tell him the number 

<image>

Input

The first line of input contains integers n and q (1 ≤ n ≤ 2 × 105 and 1 ≤ q ≤ 5 × 105).

The next n lines contain the phone numbers, i-th line contains a string si consisting of lowercase English letters (<image>).

The next q lines contain the information about the questions, each of them contains integers l, r and k (1 ≤ l ≤ r ≤ n and 1 ≤ k ≤ n).

Output

Print the answer for each question in a separate line.

Examples

Input

5 5
a
ab
abab
ababab
b
1 5 1
3 5 1
1 5 2
1 5 3
1 4 5


Output

7
5
6
3
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You've came to visit your grandma and she straight away found you a job - her Christmas tree needs decorating!

She first shows you a tree with an identified number of branches, and then hands you a some baubles (or loads of them!).

You know your grandma is a very particular person and she would like the baubles to be distributed in the orderly manner. You decide the best course of action would be to put the same number of baubles on each of the branches (if possible) or add one more bauble to some of the branches - starting from the beginning of the tree. 

In this kata you will return an array of baubles on each of the branches.

For example: 

10 baubles, 2 branches: [5,5]
5 baubles, 7 branches: [1,1,1,1,1,0,0]
12 baubles, 5 branches: [3,3,2,2,2]

The numbers of branches and baubles will be always greater or equal to 0.
If there are 0 branches return: "Grandma, we will have to buy a Christmas tree first!".

Good luck - I think your granny may have some minced pies for you if you do a good job!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
When constructing electric circuits one has to connect pairs of points using wire, preferable as short as possible. In this problem we have an empty circuit board of size $N \times M$ where we want to connect the two points $A_1$ and $A_2$ with each other using one wire, and the two points $B_1$ and $B_2$ with each other using another wire. The wires must go along the horizontal and vertical edges of the grid (see figure), and the two wires may not share a common vertex. Determine the minimum length of wire needed to do so. The wire may not go outside the circuit board.

-----Input-----
The first line contains two integers, $N$ ($2 \le N \le 100$) and $M$ ($2 \le M \le 100$), the grid size of the circuit board.

Then follows four lines containing the coordinates for the points $A_1$, $A_2$, $B_1$ and $B_2$, respectively. Each coordinate pair will be described using two integers and will correspond to an intersection point in the grid. The first coordinate will be between $0$ and $N$ inclusive and the second coordinate between $0$ and $M$ inclusive. All coordinate pairs will be unique.

-----Output-----
A single line containing the minimum length of wire needed to connect the points, or “IMPOSSIBLE” if it’s not possible to do so.

-----Examples-----
Sample Input:
6 3
2 3
4 0
0 2
6 1
Sample Output:
IMPOSSIBLE

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given the array $a$ consisting of $n$ elements and the integer $k \le n$.

You want to obtain at least $k$ equal elements in the array $a$. In one move, you can make one of the following two operations:

  Take one of the minimum elements of the array and increase its value by one (more formally, if the minimum value of $a$ is $mn$ then you choose such index $i$ that $a_i = mn$ and set $a_i := a_i + 1$);  take one of the maximum elements of the array and decrease its value by one (more formally, if the maximum value of $a$ is $mx$ then you choose such index $i$ that $a_i = mx$ and set $a_i := a_i - 1$). 

Your task is to calculate the minimum number of moves required to obtain at least $k$ equal elements in the array.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the number of elements in $a$ and the required number of equal elements.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the $i$-th element of $a$.


-----Output-----

Print one integer — the minimum number of moves required to obtain at least $k$ equal elements in the array.


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

Output
3

Input
7 5
3 3 2 1 1 1 3

Output
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Appu is now frustrated,because even after using the height doubling powder from the market, he is unable to normalize the heights of sugarcanes. Since Appu is very very stubborn, he will find a way to normalize the heights of sugarcanes by hook or crook.

Luckily Appu came to know about this "Organic Adhesive"  which can combine two pieces of sugarcane at the joints. Appu's sugarcanes are made up of individual units of length L joined together at joints. 
Using the organic adhesive, Appu can cut any piece of sugarcane at joints and glue it to other sugarcane at its joint. 

Now using this glue Appu thinks he can easily equalize the height of sugarcanes. But for this purpose he will have to buy lots and lots of  "Organic Adhesive" which costs him Rs. R per joint he makes. He needs your help to determine how much money he will require to equalize all sugarcanes using the "organic adhesive", if you think Appu can still not equalize them all print "-1".

INPUT FORMAT:

Line 1: The number of sugarcanes, N and cost per join operation made,R[Integer] (1 ≤ N ≤ 1,000, 0 ≤ R ≤ 1000).
Lines 2..1+N: Each line contains the number of joints in a single sugarcane (an integer in the range 0...1000).

OUTPUT FORMAT:

Line 1: The minimum amount of money Appu needs to spend in order to equalize heights of all the sugarcanes. If he cannot equalize the heights no matter what he does,print -1.

NOTE:
Appu can cut any sugarcane at any joint.
Appu cannot throw any sugarcane,nor any piece of it. 
If sugarcane has J joints and length of each piece or unit in sugarcane is L, then the height of sugarcane is (J+1)*L, so in simple words we have to make every sugarcane have same height, which means it must have same number of joints.
Appu must have N sugarcanes of equal height after all cutting and joining operations

HINT
When there are three sugarcanes of height 10,30 and 50 . Appu can cut the last sugarcane of height 50(30+20) into 2 sugarcanes of height 20 and 30 , and then he will use adhesive to join the smaller one with the first sugarcane of height 10 which will make it (10+20)30 as well.
So he will have to use organic adhesive only once here

SAMPLE INPUT
3 1
3
1
2

SAMPLE OUTPUT
1

Explanation

We have 3 sugarcanes of respective heights
3,2 and 4

to equalize them we will cut the sugarcane with height 4 and make it of height 3 and then we will use "organic adhesive" to join the spare sugarcane to the sugarcane with height 2, this way we can get 3 sugarcanes of height 3 each

Since we used "organic adhesive" only once, the cost will be Re. 1 /- only

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a laboratory, an assistant, Nathan Wada, is measuring weight differences between sample pieces pair by pair. He is using a balance because it can more precisely measure the weight difference between two samples than a spring scale when the samples have nearly the same weight.

He is occasionally asked the weight differences between pairs of samples. He can or cannot answer based on measurement results already obtained.

Since he is accumulating a massive amount of measurement data, it is now not easy for him to promptly tell the weight differences. Nathan asks you to develop a program that records measurement results and automatically tells the weight differences.



Input

The input consists of multiple datasets. The first line of a dataset contains two integers N and M. N denotes the number of sample pieces (2 ≤ N ≤ 100,000). Each sample is assigned a unique number from 1 to N as an identifier. The rest of the dataset consists of M lines (1 ≤ M ≤ 100,000), each of which corresponds to either a measurement result or an inquiry. They are given in chronological order.

A measurement result has the format,

! a b w

which represents the sample piece numbered b is heavier than one numbered a by w micrograms (a ≠ b). That is, w = wb − wa, where wa and wb are the weights of a and b, respectively. Here, w is a non-negative integer not exceeding 1,000,000.

You may assume that all measurements are exact and consistent.

An inquiry has the format,

? a b

which asks the weight difference between the sample pieces numbered a and b (a ≠ b).

The last dataset is followed by a line consisting of two zeros separated by a space.

Output

For each inquiry, ? a b, print the weight difference in micrograms between the sample pieces numbered a and b, wb − wa, followed by a newline if the weight difference can be computed based on the measurement results prior to the inquiry. The difference can be zero, or negative as well as positive. You can assume that its absolute value is at most 1,000,000. If the difference cannot be computed based on the measurement results prior to the inquiry, print UNKNOWN followed by a newline.

Example

Input

2 2
! 1 2 1
? 1 2
2 2
! 1 2 1
? 2 1
4 7
! 1 2 100
? 2 3
! 2 3 100
? 2 3
? 1 3
! 4 3 150
? 4 1
0 0


Output

1
-1
UNKNOWN
100
200
-50

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given Name of chef's friend and using chef's new method of calculating value of string , chef have to find the value of all the names. Since chef is busy , he asked you to do the work from him .
The method is a function $f(x)$ as follows - 
- 
$f(x)$ = $1$ , if $x$ is a consonent
- 
$f(x)$ = $0$ , if $x$ is a vowel 
Your task is to apply the above function on all the characters in the string $S$ and convert the obtained binary string in decimal number N. Since the number N can be very large, compute it modulo $10^9+7$ .
Input:
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each test line contains one String $S$ composed of lowercase English alphabet letters. 

-----Output:-----
For each case, print a single line containing one integer $N$ modulo  $10^9+7$ .

-----Constraints-----
- $1 \leq T \leq 50$
- $1 \leq |S| \leq 10^5$

-----Sample Input:-----
1
codechef

-----Sample Output:-----
173

-----EXPLANATION:-----
The string "codechef" will be converted to 10101101 ,using the chef's method function . Which is equal to 173.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Piegirl was asked to implement two table join operation for distributed database system, minimizing the network traffic.

Suppose she wants to join two tables, *A* and *B*. Each of them has certain number of rows which are distributed on different number of partitions. Table *A* is distributed on the first cluster consisting of *m* partitions. Partition with index *i* has *a**i* rows from *A*. Similarly, second cluster containing table *B* has *n* partitions, *i*-th one having *b**i* rows from *B*. 

In one network operation she can copy one row from any partition to any other partition. At the end, for each row from *A* and each row from *B* there should be a partition that has both rows. Determine the minimal number of network operations to achieve this.

Input Specification:
First line contains two integer numbers, *m* and *n* (1<=≤<=*m*,<=*n*<=≤<=105). Second line contains description of the first cluster with *m* space separated integers, *a**i* (1<=≤<=*a**i*<=≤<=109). Similarly, third line describes second cluster with *n* space separated integers, *b**i* (1<=≤<=*b**i*<=≤<=109).

Output Specification:
Print one integer — minimal number of copy operations.

Demo Input:
['2 2\n2 6\n3 100\n', '2 3\n10 10\n1 1 1\n']

Demo Output:
['11\n', '6\n']

Note:
In the first example it makes sense to move all the rows to the second partition of the second cluster which is achieved in 2 + 6 + 3 = 11 operations

In the second example Piegirl can copy each row from *B* to the both partitions of the first cluster which needs 2·3 = 6 copy operations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two words are anagrams of one another if their letters can be rearranged to form the other word.  

Given a string, split it into two contiguous substrings of equal length.  Determine the minimum number of characters to change to make the two substrings into anagrams of one another.

Example 

$s=\textbf{abccde}$  

Break $\boldsymbol{\mathrm{~S~}}$ into two parts: 'abc' and 'cde'.  Note that all letters have been used, the substrings are contiguous and their lengths are equal.  Now you can change 'a' and 'b' in the first substring to 'd' and 'e' to have 'dec' and 'cde' which are anagrams.  Two changes were necessary.

Function Description

Complete the anagram function in the editor below.    

anagram has the following parameter(s):  

string s: a string  

Returns  

int: the minimum number of characters to change or -1. 

Input Format

The first line will contain an integer, $\textit{q}$, the number of test cases. 

Each test case will contain a string $\boldsymbol{\mathrm{~S~}}$.

Constraints

$1\leq q\leq100$ 

$1\leq|s|\leq10^4$  
$\boldsymbol{\mathrm{~S~}}$ consists only of characters in the range ascii[a-z].  

Sample Input
6
aaabbb
ab
abc
mnop
xyyx
xaxbbbxx

Sample Output
3
1
-1
2
0
1

Explanation

Test Case #01: We split $\boldsymbol{\mathrm{~S~}}$ into two strings $\mbox{S1}$='aaa' and $\mbox{S2}$='bbb'.  We have to replace all three characters from the first string with 'b' to make the strings anagrams. 

Test Case #02: You have to replace 'a' with 'b', which will  generate "bb". 

Test Case #03: It is not possible for two strings of unequal length to be anagrams of one another. 

Test Case #04: We have to replace both the characters of first string ("mn") to make it an anagram of the other one. 

Test Case #05: $\mbox{S1}$ and $\mbox{S2}$ are already anagrams of one another. 

Test Case #06: Here S1 = "xaxb" and S2 = "bbxx". You must replace 'a' from S1 with 'b' so that S1 = "xbxb".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Milly is very much concern about her rank in her class. So to make her feel better , her friend Pranjul will give three numbers to her denoting N, X and Y. N represents the total number of students in the class. Now he has already described about the rank predictor algorithm that he has made for her. According to this algorithm, there are no less than X people who are better than her and no more than Y people are worse than her. Your task is to print the number of different ranks that she can predict using Pranjul's algorithm.

Input

First line will have a value of T (No. of test cases).
Then for every test case there will be one line containing three space separated values of N, X and Y.

Output

For every test case print the required answer in a new line.

Constraints

1 ≤ T ≤ 10^5.
0 ≤ X, Y  ≤ N  ≤  10^18.

SAMPLE INPUT
1
4 1 2

SAMPLE OUTPUT
3

Explanation

Ranks are : 2, 3, 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer sequence $A_1, A_2, \ldots, A_N$. For any pair of integers $(l, r)$ such that $1 \le l \le r \le N$, let's define $\mathrm{OR}(l, r)$ as $A_l \lor A_{l+1} \lor \ldots \lor A_r$. Here, $\lor$ is the bitwise OR operator.
In total, there are $\frac{N(N+1)}{2}$ possible pairs $(l, r)$, i.e. $\frac{N(N+1)}{2}$ possible values of $\mathrm{OR}(l, r)$. Determine if all these values are pairwise distinct.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing the string "YES" if all values of $\mathrm{OR}(l, r)$ are pairwise distinct or "NO" otherwise (without quotes).

-----Constraints-----
- $1 \le T \le 300$
- $1 \le N \le 10^5$
- $0 \le A_i \le 10^{18}$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $3 \cdot 10^5$

-----Example Input-----
4
3
1 2 7
2
1 2
3
6 5 8
5
12 32 45 23 47

-----Example Output-----
NO
YES
YES
NO

-----Explanation-----
Example case 1: The values of $\mathrm{OR}(l, r)$ are $1, 2, 7, 3, 7, 7$ (corresponding to the contiguous subsequences $[1], [2], [7], [1,2], [2,7], [1,2,7]$ respectively). We can see that these values are not pairwise distinct.
Example case 2: The values of $\mathrm{OR}(l, r)$ are $1, 2, 3$ (corresponding to the contiguous subsequences $[1], [2], [1, 2]$ respectively) and they are pairwise distinct.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function `insertDash(num)`/`InsertDash(int num)` that will insert dashes ('-') between each two odd numbers in num. For example: if num is 454793 the output should be 4547-9-3. Don't count zero as an odd number.

Note that the number will always be non-negative (>= 0).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function named `first_non_repeating_letter` that takes a string input, and returns the first character that is not repeated anywhere in the string.

For example, if given the input `'stress'`, the function should return `'t'`, since the letter *t* only occurs once in the string, and occurs first in the string.

As an added challenge, upper- and lowercase letters are considered the **same character**, but the function should return the correct case for the initial letter.  For example, the input `'sTreSS'` should return `'T'`.

If a string contains *all repeating characters*, it should return an empty string (`""`) or `None` -- see sample tests.

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