vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are about to organize a big programming competition. N competitors are registered for it. You know that you are going to divide all of them in some number of rooms. After the competition, each room will have its own leaderboard computed i.e. the order of competitors in that room based on their performance. You decided that after the competition, K random competitors will be awarded by lucky-one award. You will mark these lucky competitors with stars near their names on leaderboards. You set the scoring in such a way that there will be no draws between any players.

A global leaderboard is a set of leaderboards of all rooms after the competition, with exactly K lucky competitors marked with stars near their names.

You are interested in how many different global leaderboards exist.

Since the resulting number of global leaderboards can be very large, you are interested its value modulo 10^9 + 7

Input:

In the one and only line of input, there are two integers N and K, denoting the number of competitors registered for the contest and the number of competitors to be awarded by lucky-one award.

Output:

In one line, output the number of different global leaderboards.

Constraints:

1 ≤ N ≤ 1000
0 ≤ K ≤ N

SAMPLE INPUT
2 2

SAMPLE OUTPUT
3

Explanation

You can divide all competitors either in two rooms or place all of them in one room.

If you divide them into two rooms, each room will have exactly one competitor, so there is only one leaderboard possible for each such room.

If you divide them into one room, there are two possible leaderboards for that room - either the first players is better than the second, or the second is better than the first. 

At the end, you randomly award 2 competitors with the stars and since there are only 2 competitors, there is one way to do it in both above cases.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alena has successfully passed the entrance exams to the university and is now looking forward to start studying.

One two-hour lesson at the Russian university is traditionally called a pair, it lasts for two academic hours (an academic hour is equal to 45 minutes).

The University works in such a way that every day it holds exactly n lessons. Depending on the schedule of a particular group of students, on a given day, some pairs may actually contain classes, but some may be empty (such pairs are called breaks).

The official website of the university has already published the schedule for tomorrow for Alena's group. Thus, for each of the n pairs she knows if there will be a class at that time or not.

Alena's House is far from the university, so if there are breaks, she doesn't always go home. Alena has time to go home only if the break consists of at least two free pairs in a row, otherwise she waits for the next pair at the university.

Of course, Alena does not want to be sleepy during pairs, so she will sleep as long as possible, and will only come to the first pair that is presented in her schedule. Similarly, if there are no more pairs, then Alena immediately goes home.

Alena appreciates the time spent at home, so she always goes home when it is possible, and returns to the university only at the beginning of the next pair. Help Alena determine for how many pairs she will stay at the university. Note that during some pairs Alena may be at the university waiting for the upcoming pair.


-----Input-----

The first line of the input contains a positive integer n (1 ≤ n ≤ 100) — the number of lessons at the university. 

The second line contains n numbers a_{i} (0 ≤ a_{i} ≤ 1). Number a_{i} equals 0, if Alena doesn't have the i-th pairs, otherwise it is equal to 1. Numbers a_1, a_2, ..., a_{n} are separated by spaces.


-----Output-----

Print a single number — the number of pairs during which Alena stays at the university.


-----Examples-----
Input
5
0 1 0 1 1

Output
4

Input
7
1 0 1 0 0 1 0

Output
4

Input
1
0

Output
0



-----Note-----

In the first sample Alena stays at the university from the second to the fifth pair, inclusive, during the third pair she will be it the university waiting for the next pair. 

In the last sample Alena doesn't have a single pair, so she spends all the time at home.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An ordered sequence of numbers from 1 to N is given. One number might have deleted from it, then the remaining numbers were mixed. Find the number that was deleted.

Example: 
 - The starting array sequence is `[1,2,3,4,5,6,7,8,9]`
 - The mixed array with one deleted number is `[3,2,4,6,7,8,1,9]`
 - Your function should return the int `5`.

If no number was deleted from the array and no difference with it, your function should return the int `0`.

Note that N may be 1 or less (in the latter case, the first array will be `[]`).

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

Write a function that accepts two arguments and generates a sequence containing the integers from the first argument to the second inclusive. 

## Input

Pair of integers greater than or equal to `0`. The second argument will always be greater than or equal to the first. 

## Example

```python
generate_integers(2, 5) # --> [2, 3, 4, 5]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Have you ever implemented a program adding two big integers that cannot be represented by the primitive data type of your programming language? The algorithm is just simulation of the column addition method that we have been taught in elementary school. Sometimes we forget the carry and the result is incorrect. 
 In this problem, you need to evaluate the expected value of the number of times we have non-zero carry when adding two non-negative integers that contain at most N digits each. Note that we are adding the numbers in their base 10 representation.

For example, the following table shows the number of carries when adding some pairs of numbers: 


A
B
Number of carries


20
4
0


111
119
1


123
923
1


1235
98765
5



Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case has a single line containing an integer N.

Output
For each test case, output a single line containing the required expected value.
Your answer will be accepted if the error is less than 10 ^-6.

Constraints

1 ≤ T ≤ 100,000(10^5)
1 ≤ N ≤ 100,000(10^5)


Example
Input:
3
1
2
3

Output:
0.45
0.945
1.4445


Explanation
Example case 1.
We have 10*10 = 100 cases of adding two 1-digit number.
The carry appears when adding 1 and 9, 2 and 9, 3 and 9 ... and so on,
there are 45 cases in total and in each case, the carry appears exactly once.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Goshtasp was known to be a good programmer in his school. One day Vishtasp, Goshtasp's friend, asked him to solve this task:

Given a positive integer n, you should determine whether n is rich.

The positive integer x is rich, if there exists some set of distinct numbers a1, a2, ..., am such that <image>. In addition: every ai should be either a prime number, or equal to 1.

Vishtasp said that he would share his Eidi 50 / 50 with Goshtasp, if he could solve the task. Eidi is money given to children for Noruz by their parents and/or relatives.

Goshtasp needs to solve this problem to get money, you need to solve it to get score!

Input

Input contains a single positive integer n (1 ≤ n ≤ 10000).

Output

If the number is not rich print 0. Otherwise print the numbers a1, ..., am. If several solutions exist print the lexicographically latest solution. Answers are compared as sequences of numbers, not as strings.

For comparing two sequences a1, ..., am and b1, ..., bn we first find the first index i such that ai ≠ bi, if ai < bi then a is lexicographically earlier and if bi < ai then b is lexicographically earlier. If m ≠ n we add zeroes at the end of the smaller sequence (only for the moment of comparison) and then perform the comparison.

You do not need to minimize the number of elements in sequence (i.e. m). You just need to print the lexicographically latest solution.

See samples to find out how to print the sequence.

Examples

Input

11


Output

11=11


Input

545


Output

541+3+1=545

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer N, print all the divisors of N in the ascending order.
 
Example 1:
Input : 20
Output: 1 2 4 5 10 20
Explanation: 20 is completely 
divisible by 1, 2, 4, 5, 10 and 20.
Example 2:
Input: 21191
Output: 1 21191
Explanation: As 21191 is a prime number,
it has only 2 factors(1 and the number itself).
Your Task:
Your task is to complete the function print_divisors() which takes N as input parameter and prints all the factors of N as space seperated integers in sorted order. You don't have to print any new line after printing the desired output. It will be handled in driver code.
 
Expected Time Complexity: O(sqrt(N))
Expected Space Complexity: O(sqrt(N))
 
Constraints:
1 <= N <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Valera has array a, consisting of n integers a_0, a_1, ..., a_{n} - 1, and function f(x), taking an integer from 0 to 2^{n} - 1 as its single argument. Value f(x) is calculated by formula $f(x) = \sum_{i = 0}^{n - 1} a_{i} \cdot b i t(i)$, where value bit(i) equals one if the binary representation of number x contains a 1 on the i-th position, and zero otherwise.

For example, if n = 4 and x = 11 (11 = 2^0 + 2^1 + 2^3), then f(x) = a_0 + a_1 + a_3.

Help Valera find the maximum of function f(x) among all x, for which an inequality holds: 0 ≤ x ≤ m.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of array elements. The next line contains n space-separated integers a_0, a_1, ..., a_{n} - 1 (0 ≤ a_{i} ≤ 10^4) — elements of array a.

The third line contains a sequence of digits zero and one without spaces s_0s_1... s_{n} - 1 — the binary representation of number m. Number m equals $\sum_{i = 0}^{n - 1} 2^{i} \cdot s_{i}$.


-----Output-----

Print a single integer — the maximum value of function f(x) for all $x \in [ 0 . . m ]$.


-----Examples-----
Input
2
3 8
10

Output
3

Input
5
17 0 10 2 1
11010

Output
27



-----Note-----

In the first test case m = 2^0 = 1, f(0) = 0, f(1) = a_0 = 3.

In the second sample m = 2^0 + 2^1 + 2^3 = 11, the maximum value of function equals f(5) = a_0 + a_2 = 17 + 10 = 27.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:


Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:


Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.


Note:

Your solution should be in logarithmic complexity.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Petya likes points a lot. Recently his mom has presented him *n* points lying on the line *OX*. Now Petya is wondering in how many ways he can choose three distinct points so that the distance between the two farthest of them doesn't exceed *d*.

Note that the order of the points inside the group of three chosen points doesn't matter.

Input Specification:
The first line contains two integers: *n* and *d* (1<=≤<=*n*<=≤<=105; 1<=≤<=*d*<=≤<=109). The next line contains *n* integers *x*1,<=*x*2,<=...,<=*x**n*, their absolute value doesn't exceed 109 — the *x*-coordinates of the points that Petya has got.

It is guaranteed that the coordinates of the points in the input strictly increase.

Output Specification:
Print a single integer — the number of groups of three points, where the distance between two farthest points doesn't exceed *d*.

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

Demo Input:
['4 3\n1 2 3 4\n', '4 2\n-3 -2 -1 0\n', '5 19\n1 10 20 30 50\n']

Demo Output:
['4\n', '2\n', '1\n']

Note:
In the first sample any group of three points meets our conditions.

In the seconds sample only 2 groups of three points meet our conditions: {-3, -2, -1} and {-2, -1, 0}.

In the third sample only one group does: {1, 10, 20}.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Many modern text editors automatically check the spelling of the user's text. Some editors even suggest how to correct typos.

In this problem your task to implement a small functionality to correct two types of typos in a word. We will assume that three identical letters together is a typo (for example, word "helllo" contains a typo). Besides, a couple of identical letters immediately followed by another couple of identical letters is a typo too (for example, words "helloo" and "wwaatt" contain typos).

Write a code that deletes the minimum number of letters from a word, correcting described typos in the word. You are allowed to delete letters from both ends and from the middle of the word.

Input Specification:
The single line of the input contains word *s*, its length is from 1 to 200000 characters. The given word *s* consists of lowercase English letters.

Output Specification:
Print such word *t* that it doesn't contain any typos described in the problem statement and is obtained from *s* by deleting the least number of letters.

If there are multiple solutions, print any of them.

Demo Input:
['helloo\n', 'woooooow\n']

Demo Output:
['hello\n', 'woow\n']

Note:
The second valid answer to the test from the statement is "heloo".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a singly linked list, delete middle of the linked list. For example, if given linked list is 1->2->3->4->5 then linked list should be modified to 1->2->4->5.
If there are even nodes, then there would be two middle nodes, we need to delete the second middle element. For example, if given linked list is 1->2->3->4->5->6 then it should be modified to 1->2->3->5->6.
If the input linked list is NULL or has 1 node, then it should return NULL
Example 1:
Input:
LinkedList: 1->2->3->4->5
Output: 1 2 4 5
Example 2:
Input:
LinkedList: 2->4->6->7->5->1
Output: 2 4 6 5 1
Your Task:
The task is to complete the function deleteMid() which should delete the middle element from the linked list and return the head of the modified linked list. If the linked list is empty then it should return NULL.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 1000
1 <= value <= 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mahmoud and Ehab solved Dr. Evil's questions so he gave them the password of the door of the evil land. When they tried to open the door using it, the door gave them a final question to solve before they leave (yes, the door is digital, Dr. Evil is modern). If they don't solve it, all the work will be useless and they won't leave the evil land forever. Will you help them?

Mahmoud and Ehab are given n strings s1, s2, ... , sn numbered from 1 to n and q queries, Each query has one of the following forms:

  * 1 a b (1 ≤ a ≤ b ≤ n), For all the intervals [l;r] where (a ≤ l ≤ r ≤ b) find the maximum value of this expression:

(r - l + 1) * LCP(sl, sl + 1, ... , sr - 1, sr) where LCP(str1, str2, str3, ... ) is the length of the longest common prefix of the strings str1, str2, str3, ... .

  * 2 x y (1 ≤ x ≤ n) where y is a string, consisting of lowercase English letters. Change the string at position x to y.

Input

The first line of input contains 2 integers n and q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105) – The number of strings and the number of queries, respectively.

The second line contains n strings stri consisting of lowercase English letters.

The next q lines describe the queries and may have one of the 2 forms:

  * 1 a b (1 ≤ a ≤ b ≤ n).
  * 2 x y (1 ≤ x ≤ n), where y is a string consisting of lowercase English letters.



the total length of all strings in input won't exceed 105

Output

For each query of first type output its answer in a new line.

Example

Input

5 9
mahmoud mahmoudbadawy drmahmoud drevil mahmoud
1 1 5
1 1 2
1 2 3
2 3 mahmoud
2 4 mahmoud
2 2 mahmouu
1 1 5
1 2 3
1 1 1


Output

14
14
13
30
12
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Wire Less is not that good at implementing circuit in a breadboard. In his Digital Logic Design course, he has to implement several boolean functions using the breadboard. In a breadboard, inputs are given through the switches and outputs are taken through the LEDs. Each input switch can be either in ground state or in high state. So, if he wishes to implement a boolean function, f(x1, x2, .., xn) that takes n boolean values as input and returns m boolean values as output, he will use n switches and m LEDs. 
Mr. Wire Less can quickly assemble the necessary ICs and wires, but the key problem is testing. While testing he has to check with all possible input combination, to make sure whether the output of LED corresponds to the expected output or not. This is taking too long for him, as most of the switches are jammed and difficult to toggle. 
Mr. Wire Less is asking for help to minimize his time of testing. So, your task is to minimize the total number of switch-toggle throughout the testing.
For example, if Mr. Wire Less has to test a function f(x0, x1) of two variables, he may choose this switching-sequence for testing 00, 11, 10, 01. In this case, the total number of switch-toggle will be 2+1+2 = 5. But if he tests in this sequence 00, 10, 11, 01 total number of toggle will be 1+1+1 = 3.
Given n, you have to output the minimum number of toggle needed for complete testing. Though it seems impractical, he wants you to solve the problem for a very large value of n. But, then the toggle value can be quite big. So, he is completely okay with the toggle value modulo 8589934592 (233).  

-----Input-----
The first line of the input contains a positive integer T(T ≤ 105), denoting the number of test-case. Each of the following T lines contains a single non-negative integer n(n ≤ 1020).

-----Output-----
For every test-case, output a single containing test-case number and the minimum number of switch-toggle modulo 8589934592 (233).

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

Output
Case 1: 1
Case 2: 3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya and Vasya are playing a game. Petya's got *n* non-transparent glasses, standing in a row. The glasses' positions are indexed with integers from 1 to *n* from left to right. Note that the positions are indexed but the glasses are not.

First Petya puts a marble under the glass in position *s*. Then he performs some (possibly zero) shuffling operations. One shuffling operation means moving the glass from the first position to position *p*1, the glass from the second position to position *p*2 and so on. That is, a glass goes from position *i* to position *p**i*. Consider all glasses are moving simultaneously during one shuffling operation. When the glasses are shuffled, the marble doesn't travel from one glass to another: it moves together with the glass it was initially been put in.

After all shuffling operations Petya shows Vasya that the ball has moved to position *t*. Vasya's task is to say what minimum number of shuffling operations Petya has performed or determine that Petya has made a mistake and the marble could not have got from position *s* to position *t*.

Input Specification:
The first line contains three integers: *n*,<=*s*,<=*t* (1<=≤<=*n*<=≤<=105; 1<=≤<=*s*,<=*t*<=≤<=*n*) — the number of glasses, the ball's initial and final position. The second line contains *n* space-separated integers: *p*1,<=*p*2,<=...,<=*p**n* (1<=≤<=*p**i*<=≤<=*n*) — the shuffling operation parameters. It is guaranteed that all *p**i*'s are distinct.

Note that *s* can equal *t*.

Output Specification:
If the marble can move from position *s* to position *t*, then print on a single line a non-negative integer — the minimum number of shuffling operations, needed to get the marble to position *t*. If it is impossible, print number -1.

Demo Input:
['4 2 1\n2 3 4 1\n', '4 3 3\n4 1 3 2\n', '4 3 4\n1 2 3 4\n', '3 1 3\n2 1 3\n']

Demo Output:
['3\n', '0\n', '-1\n', '-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Haha, try to solve this, SelectorUnlimited!

— antontrygubO_o

Your friends Alice and Bob practice fortune telling.

Fortune telling is performed as follows. There is a well-known array $a$ of $n$ non-negative integers indexed from $1$ to $n$. The tellee starts with some non-negative number $d$ and performs one of the two operations for each $i = 1, 2, \ldots, n$, in the increasing order of $i$. The possible operations are:

replace their current number $d$ with $d + a_i$

replace their current number $d$ with $d \oplus a_i$ (hereinafter $\oplus$ denotes the bitwise XOR operation )

Notice that the chosen operation may be different for different $i$ and for different tellees.

One time, Alice decided to start with $d = x$ and Bob started with $d = x + 3$. Each of them performed fortune telling and got a particular number in the end. Notice that the friends chose operations independently of each other, that is, they could apply different operations for the same $i$.

You learnt that either Alice or Bob ended up with number $y$ in the end, but you don't know whose of the two it was. Given the numbers Alice and Bob started with and $y$, find out who (Alice or Bob) could get the number $y$ after performing the operations. It is guaranteed that on the jury tests, exactly one of your friends could have actually gotten that number.

Hacks

You cannot make hacks in this problem.


-----Input-----

On the first line of the input, you are given one number $t$ ($1 \le t \le 10^4$) — the number of test cases. The following $2 \cdot t$ lines contain test cases.

The first line of each test case contains three numbers $n$, $x$, $y$ ($1 \le n \le 10^5$, $0 \le x \le 10^9$, $0 \le y \le 10^{15}$) — the length of array $a$, Alice's initial number (Bob's initial number is therefore $x+3$), and the number that one of the two friends got in the end.

The second line of each test case contains $n$ numbers — the array $a$ ($0 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, print the name of the friend who could get the number $y$: "Alice" or "Bob".


-----Examples-----

Input
4
1 7 9
2
2 0 2
1 3
4 0 1
1 2 3 4
2 1000000000 3000000000
1000000000 1000000000
Output
Alice
Alice
Bob
Alice


-----Note-----

In the first test case, Alice could get $9$ using the following operations: $7 + 2 = 9$.

In the second test case, Alice could get $2$ using this operations: $(0 + 1) \oplus 3 = 2$.

In the third test case, Bob started with $x+3 = 0+3=3$ and could get $1$ this way: $(((3 + 1) + 2) \oplus 3) \oplus 4 = 1$.

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