vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
JATC loves Banh-mi (a Vietnamese food). His affection for Banh-mi is so much that he always has it for breakfast. This morning, as usual, he buys a Banh-mi and decides to enjoy it in a special way.

First, he splits the Banh-mi into $n$ parts, places them on a row and numbers them from $1$ through $n$. For each part $i$, he defines the deliciousness of the part as $x_i \in \{0, 1\}$. JATC's going to eat those parts one by one. At each step, he chooses arbitrary remaining part and eats it. Suppose that part is the $i$-th part then his enjoyment of the Banh-mi will increase by $x_i$ and the deliciousness of all the remaining parts will also increase by $x_i$. The initial enjoyment of JATC is equal to $0$.

For example, suppose the deliciousness of $3$ parts are $[0, 1, 0]$. If JATC eats the second part then his enjoyment will become $1$ and the deliciousness of remaining parts will become $[1, \_, 1]$. Next, if he eats the first part then his enjoyment will become $2$ and the remaining parts will become $[\_, \_, 2]$. After eating the last part, JATC's enjoyment will become $4$.

However, JATC doesn't want to eat all the parts but to save some for later. He gives you $q$ queries, each of them consisting of two integers $l_i$ and $r_i$. For each query, you have to let him know what is the maximum enjoyment he can get if he eats all the parts with indices in the range $[l_i, r_i]$ in some order.

All the queries are independent of each other. Since the answer to the query could be very large, print it modulo $10^9+7$.


-----Input-----

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 100\,000$).

The second line contains a string of $n$ characters, each character is either '0' or '1'. The $i$-th character defines the deliciousness of the $i$-th part.

Each of the following $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the segment of the corresponding query.


-----Output-----

Print $q$ lines, where $i$-th of them contains a single integer — the answer to the $i$-th query modulo $10^9 + 7$.


-----Examples-----
Input
4 2
1011
1 4
3 4

Output
14
3

Input
3 2
111
1 2
3 3

Output
3
1



-----Note-----

In the first example:   For query $1$: One of the best ways for JATC to eats those parts is in this order: $1$, $4$, $3$, $2$.  For query $2$: Both $3$, $4$ and $4$, $3$ ordering give the same answer. 

In the second example, any order of eating parts leads to the same answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
I started this as a joke among friends, telling that converting numbers to other integer bases is for n00bs, while an actual coder at least converts numbers to more complex bases like [pi (or π or however you wish to spell it in your language)](http://en.wikipedia.org/wiki/Pi), so they dared me proving I was better.

And I did it in few hours, discovering that what I started as a joke actually has [some math ground and application (particularly the conversion to base pi, it seems)](http://en.wikipedia.org/wiki/Non-integer_representation).

That said, now I am daring you to do the same, that is to build a function so that it takes a **number** (any number, you are warned!) and optionally the **number of decimals** (default: 0) and a **base** (default: pi), returning the proper conversion **as a string**:

#Note
In Java there is no easy way with optional parameters so all three parameters will be given; the same in C# because, as of now, the used version is not known. 

```python
converter(13) #returns '103'
converter(13,3) #returns '103.010'
converter(-13,0,2) #returns '-1101'
```

I know most of the world uses a comma as a [decimal mark](http://en.wikipedia.org/wiki/Decimal_mark), but as English language and culture are *de facto* the Esperanto of us coders, we will stick to our common glorious traditions and uses, adopting the trivial dot (".") as decimal separator; if the absolute value of the result is <1, you have of course to put one (and only one) leading 0 before the decimal separator.

Finally, you may assume that decimals if provided will always be >= 0 and that no test base will be smaller than 2 (because, you know, converting to base 1 is pretty lame) or greater than 36; as usual, for digits greater than 9 you can use uppercase alphabet letter, so your base of numeration is going to be: '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'.

That is my first 3-languages-kata, so I count on you all to give me extensive feedback, no matter how harsh it may sound, so to improve myself even further :)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rahul loves Fibonacci number . He has been given a question .

Find  :  (A^B) % M

where,

A =   Nth non-fibonacci number

B =   (Nth fibonacci number) % M

M=   10^9 + 7

Consider Fibonacci series as 1,1,2,3,....

Help Rahul to solve this question by writing code for him!

Note: It is guaranteed that Nth non-Fibonacci number will always be less than the value of M for every value of N used in the problem.

Input:

First line contains T , the number of test cases.

Each next T lines contains a  number N.

Output:

Print T lines of output where each line corresponds to the required answer. 

Constraints:

1 ≤ T ≤100000

1 ≤ N ≤9*10^8

SAMPLE INPUT
3
3
2
1

SAMPLE OUTPUT
49
6
4

Explanation

For N=3 : 3rd non fibo number =7, 3rd fibo number=2. ans= (7^2)%M=49

For N=2 : 2nd non fibo number =6, 2nd fibo number=1. ans=(6^1)%M=6

For N=1 : 1st non fibo number =4, 1st fibo number=1.  ans= (4^1)%M=4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya got an array consisting of n numbers, it is the gift for his birthday. Now he wants to sort it in the non-decreasing order. However, a usual sorting is boring to perform, that's why Petya invented the following limitation: one can swap any two numbers but only if at least one of them is lucky. Your task is to sort the array according to the specified limitation. Find any possible sequence of the swaps (the number of operations in the sequence should not exceed 2n).

Input

The first line contains an integer n (1 ≤ n ≤ 105) — the number of elements in the array. The second line contains n positive integers, not exceeding 109 — the array that needs to be sorted in the non-decreasing order.

Output

On the first line print number k (0 ≤ k ≤ 2n) — the number of the swaps in the sorting. On the following k lines print one pair of distinct numbers (a pair per line) — the indexes of elements to swap. The numbers in the array are numbered starting from 1. If it is impossible to sort the given sequence, print the single number -1.

If there are several solutions, output any. Note that you don't have to minimize k. Any sorting with no more than 2n swaps is accepted.

Examples

Input

2
4 7


Output

0


Input

3
4 2 1


Output

1
1 3


Input

7
77 66 55 44 33 22 11


Output

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're given a list of n strings a_1, a_2, ..., a_{n}. You'd like to concatenate them together in some order such that the resulting string would be lexicographically smallest.

Given the list of strings, output the lexicographically smallest concatenation.


-----Input-----

The first line contains integer n — the number of strings (1 ≤ n ≤ 5·10^4).

Each of the next n lines contains one string a_{i} (1 ≤ |a_{i}| ≤ 50) consisting of only lowercase English letters. The sum of string lengths will not exceed 5·10^4.


-----Output-----

Print the only string a — the lexicographically smallest string concatenation.


-----Examples-----
Input
4
abba
abacaba
bcd
er

Output
abacabaabbabcder

Input
5
x
xx
xxa
xxaa
xxaaa

Output
xxaaaxxaaxxaxxx

Input
3
c
cb
cba

Output
cbacbc

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer array and another integer element. The task is to find if the given element is present in array or not.
Example 1:
Input:
n = 4
arr[] = {1,2,3,4}
x = 3
Output: 2
Explanation: There is one test case 
with array as {1, 2, 3 4} and element 
to be searched as 3.  Since 3 is 
present at index 2, output is 2.
Example 2:
Input:
n = 5
arr[] = {1,2,3,4,5}
x = 5
Output: 4
Explanation: For array elements 
{1,2,3,4,5} element to be searched 
is 5 and it is at index 4. So, the 
output is 4.
Your Task:
The task is to complete the function search() which takes the array arr[], its size N and the element X as inputs and returns the index of first occurrence of X in the given array. If the element X does not exist in the array, the function should return -1.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1). 
Constraints:
1 <= n <= 10^{6}
0 <= arr[i] <= 10^{6}
0 <= x <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Captain Flint and his crew keep heading to a savage shore of Byteland for several months already, drinking rum and telling stories. In such moments uncle Bogdan often remembers his nephew Denis. Today, he has told a story about how Denis helped him to come up with an interesting problem and asked the crew to solve it.

In the beginning, uncle Bogdan wrote on a board a positive integer $x$ consisting of $n$ digits. After that, he wiped out $x$ and wrote integer $k$ instead, which was the concatenation of binary representations of digits $x$ consists of (without leading zeroes). For example, let $x = 729$, then $k = 111101001$ (since $7 = 111$, $2 = 10$, $9 = 1001$).

After some time, uncle Bogdan understood that he doesn't know what to do with $k$ and asked Denis to help. Denis decided to wipe last $n$ digits of $k$ and named the new number as $r$.

As a result, Denis proposed to find such integer $x$ of length $n$ that $r$ (as number) is maximum possible. If there are multiple valid $x$ then Denis is interested in the minimum one.

All crew members, including captain Flint himself, easily solved the task. All, except cabin boy Kostya, who was too drunk to think straight. But what about you?

Note: in this task, we compare integers ($x$ or $k$) as numbers (despite what representations they are written in), so $729 < 1999$ or $111 < 1000$.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Next $t$ lines contain test cases — one per test case. The one and only line of each test case contains the single integer $n$ ($1 \le n \le 10^5$) — the length of the integer $x$ you need to find.

It's guaranteed that the sum of $n$ from all test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print the minimum integer $x$ of length $n$ such that obtained by Denis number $r$ is maximum possible.


-----Example-----
Input
2
1
3

Output
8
998



-----Note-----

In the second test case (with $n = 3$), if uncle Bogdan had $x = 998$ then $k = 100110011000$. Denis (by wiping last $n = 3$ digits) will obtain $r = 100110011$.

It can be proved that the $100110011$ is the maximum possible $r$ Denis can obtain and $998$ is the minimum $x$ to obtain it.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A correct expression of the form a+b=c was written; *a*, *b* and *c* are non-negative integers without leading zeros. In this expression, the plus and equally signs were lost. The task is to restore the expression. In other words, one character '+' and one character '=' should be inserted into given sequence of digits so that: 
 -  character'+' is placed on the left of character '=', -  characters '+' and '=' split the sequence into three non-empty subsequences consisting of digits (let's call the left part a, the middle part — b and the right part — c), -  all the three parts a, b and c do not contain leading zeros, -  it is true that a+b=c. 
It is guaranteed that in given tests answer always exists.

Input Specification:
The first line contains a non-empty string consisting of digits. The length of the string does not exceed 106.

Output Specification:
Output the restored expression. If there are several solutions, you can print any of them.

Note that the answer at first should contain two terms (divided with symbol '+'), and then the result of their addition, before which symbol'=' should be. 

Do not separate numbers and operation signs with spaces. Strictly follow the output format given in the examples.

If you remove symbol '+' and symbol '=' from answer string you should get a string, same as string from the input data.

Demo Input:
['12345168\n', '099\n', '199100\n', '123123123456456456579579579\n']

Demo Output:
['123+45=168\n', '0+9=9\n', '1+99=100\n', '123123123+456456456=579579579\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Let's introduce the designation , where *x* is a string, *n* is a positive integer and operation "<=+<=" is the string concatenation operation. For example, [*abc*,<=2]<==<=*abcabc*.

We'll say that string *s* can be obtained from string *t*, if we can remove some characters from string *t* and obtain string *s*. For example, strings *ab* and *aсba* can be obtained from string *xacbac*, and strings *bx* and *aaa* cannot be obtained from it.

Sereja has two strings, *w*<==<=[*a*,<=*b*] and *q*<==<=[*c*,<=*d*]. He wants to find such maximum integer *p* (*p*<=&gt;<=0), that [*q*,<=*p*] can be obtained from string *w*.

Input Specification:
The first line contains two integers *b*, *d* (1<=≤<=*b*,<=*d*<=≤<=107). The second line contains string *a*. The third line contains string *c*. The given strings are not empty and consist of lowercase English letters. Their lengths do not exceed 100.

Output Specification:
In a single line print an integer — the largest number *p*. If the required value of *p* doesn't exist, print 0.

Demo Input:
['10 3\nabab\nbab\n']

Demo Output:
['3\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a grid of size M x N, where each square is colored with some random color among K colors with each having equal probability.

A Good Rectangle is defined as one where all squares lying on the inner border are of the same color.

What is the expected number of Good Rectangles in the given grid.

-----Input-----

- 
First Line contains M, N, K

-----Output-----
A single value rounded off to the nearest Integer corresponding to the required answer.

-----Constraints-----
-  1 <= N <= 105 
-  1 <= M <= 105 
-  1 <= K <= 105 

-----Example-----
Input:
1 3 1
Output:
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya is a beginner programmer. He has already mastered the basics of the C++ language and moved on to learning algorithms. The first algorithm he encountered was insertion sort. Petya has already written the code that implements this algorithm and sorts the given integer zero-indexed array a of size n in the non-decreasing order. for (int i = 1; i < n; i = i + 1)

{

   int j = i; 

   while (j > 0 && a[j] < a[j - 1])

   {

      swap(a[j], a[j - 1]); // swap elements a[j] and a[j - 1]

      j = j - 1;

   }

}



Petya uses this algorithm only for sorting of arrays that are permutations of numbers from 0 to n - 1. He has already chosen the permutation he wants to sort but he first decided to swap some two of its elements. Petya wants to choose these elements in such a way that the number of times the sorting executes function swap, was minimum. Help Petya find out the number of ways in which he can make the swap and fulfill this requirement.

It is guaranteed that it's always possible to swap two elements of the input permutation in such a way that the number of swap function calls decreases.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 5000) — the length of the permutation. The second line contains n different integers from 0 to n - 1, inclusive — the actual permutation.


-----Output-----

Print two integers: the minimum number of times the swap function is executed and the number of such pairs (i, j) that swapping the elements of the input permutation with indexes i and j leads to the minimum number of the executions.


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

Output
3 2

Input
5
1 2 3 4 0

Output
3 4



-----Note-----

In the first sample the appropriate pairs are (0, 3) and (0, 4). 

In the second sample the appropriate pairs are (0, 4), (1, 4), (2, 4) and (3, 4).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The academic year has just begun, but lessons and olympiads have already occupied all the free time. It is not a surprise that today Olga fell asleep on the Literature. She had a dream in which she was on a stairs. 

The stairs consists of n steps. The steps are numbered from bottom to top, it means that the lowest step has number 1, and the highest step has number n. Above each of them there is a pointer with the direction (up or down) Olga should move from this step. As soon as Olga goes to the next step, the direction of the pointer (above the step she leaves) changes. It means that the direction "up" changes to "down", the direction "down"  —  to the direction "up".

Olga always moves to the next step in the direction which is shown on the pointer above the step. 

If Olga moves beyond the stairs, she will fall and wake up. Moving beyond the stairs is a moving down from the first step or moving up from the last one (it means the n-th) step. 

In one second Olga moves one step up or down according to the direction of the pointer which is located above the step on which Olga had been at the beginning of the second. 

For each step find the duration of the dream if Olga was at this step at the beginning of the dream.

Olga's fall also takes one second, so if she was on the first step and went down, she would wake up in the next second.


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 10^6) — the number of steps on the stairs.

The second line contains a string s with the length n — it denotes the initial direction of pointers on the stairs. The i-th character of string s denotes the direction of the pointer above i-th step, and is either 'U' (it means that this pointer is directed up), or 'D' (it means this pointed is directed down).

The pointers are given in order from bottom to top.


-----Output-----

Print n numbers, the i-th of which is equal either to the duration of Olga's dream or to  - 1 if Olga never goes beyond the stairs, if in the beginning of sleep she was on the i-th step.


-----Examples-----
Input
3
UUD

Output
5 6 3 
Input
10
UUDUDUUDDU

Output
5 12 23 34 36 27 18 11 6 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s of lower and upper case English letters.
A good string is a string which doesn't have two adjacent characters s[i] and s[i + 1] where:

0 <= i <= s.length - 2
s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.

To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.
Return the string after making it good. The answer is guaranteed to be unique under the given constraints.
Notice that an empty string is also good.
 
Example 1:
Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".

Example 2:
Input: s = "abBAcC"
Output: ""
Explanation: We have many possible scenarios, and all lead to the same answer. For example:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

Example 3:
Input: s = "s"
Output: "s"

 
Constraints:

1 <= s.length <= 100
s contains only lower and upper case English letters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string S of lowercase alphabet characters and the task is to find its matching decimal representation as on the shown keypad. Output the decimal representation corresponding to the string. For ex: if you are given amazon then its corresponding decimal representation will be 262966.
Example 1:
Input:
S = geeksforgeeks
Output: 4335736743357
Explanation:geeksforgeeks is 4335736743357
in decimal when we type it using the given
keypad.
Example 2:
Input:
S = geeksquiz
Output: 433577849
Explanation: geeksquiz is 433577849 in
decimal when we type it using the given
keypad.
Your Task:
Complete printNumber() function that takes string s and its length as parameters and returns the corresponding decimal representation of the given string as a string type. The printing is done by the driver code.
Constraints:
1 ≤ length of String ≤ 100
Expected Time Complexity : O(n)
Expected Auxilliary Space : O(n)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
HAI  
    I HAS A TUX  
    GIMMEH TUX  
    I HAS A FOO ITS 0  
    I HAS A BAR ITS 0  
    I HAS A BAZ ITS 0  
    I HAS A QUZ ITS 1  
    TUX IS NOW A NUMBR  
    IM IN YR LOOP NERFIN YR TUX TIL BOTH SAEM TUX AN 0  
    I HAS A PUR  
    GIMMEH PUR  
    PUR IS NOW A NUMBR  
    FOO R SUM OF FOO AN PUR  
    BAR R SUM OF BAR AN 1  
    BOTH SAEM BIGGR OF PRODUKT OF FOO AN QUZ AN PRODUKT OF BAR BAZ AN PRODUKT OF FOO AN QUZ  
    O RLY?  
    YA RLY  
    BAZ R FOO  
    QUZ R BAR  
    OIC  
    IM OUTTA YR LOOP  
    BAZ IS NOW A NUMBAR  
    VISIBLE SMOOSH QUOSHUNT OF BAZ QUZ  
    KTHXBYE  
    

Input

The input contains between 1 and 10 lines, i-th line contains an integer number xi (0 ≤ xi ≤ 9).

Output

Output a single real number. The answer is considered to be correct if its absolute or relative error does not exceed 10 - 4.

Examples

Input

3
0
1
1


Output

0.666667

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