vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Zapray really loves the Algorithmic Problem Solving course, but he is struggling with it. Recently the class studied Longest Increasing Subsequence (LIS). Zapray knows well how to compute the length of LIS for a given sequence. But on the exam paper there appears to be a different question: “We say an element in a sequence is critical, if removing it will cause the sequence’s LIS length to decrease. Can you find all the critical elements in the sequence below?” Zapray soon realizes that this is a much bigger challenge.

-----Input-----
The input starts with a single integer $n$ ($2 \leq n \leq 10^5$), the length of the given sequence. The next line has $n$ integers giving the numbers in the sequence. The given sequence is a permutation in which each integer from $1$ to $n$ appears exactly once.

-----Output-----
Output all critical elements in the sequence in ascending order. If none of the elements are critical, output “-1”.

-----Examples-----
Sample Input 1:
4
1 3 2 4
Sample Output 1:
1 4

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

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Reverse_flash lost his power while moving through a number of timezones and landed in the timezone of Flash. Now we know that Flash would kill him as soon as he finds him.
Your job is to protect the bad.
The timezone of Flash is  (1,1). There is a safe timezone (n,n), the last one ,where Flash couldn't enter.
Timezone which Reverse_flash could pass through/enter is represented by 0 and which he couldn't is represented by 1.Now your task to find the possible number of ways to reach timezone (n,n) from (1,1).
Input format & constraints
1st line --> integer value 'n'  (n ≤ 100) denoting the size of the grid of timezones.
Next n lines -->each line contains n space separated integers either 1 or 0.
Output format
A line with possible number of ways you could protect bad from good i.e, all possible ways you could make him reach (n,n) from (1,1).

SAMPLE INPUT
7
0 0 0 0 0 0 0
0 1 0 1 0 1 0
0 0 0 0 0 0 0
0 1 0 1 0 1 0
0 0 0 0 0 0 0
0 1 0 1 0 1 0
0 0 0 0 0 0 0

SAMPLE OUTPUT
184

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Assume we take a number `x` and perform any one of the following operations:
```Pearl
a) Divide x by 3 (if it is divisible by 3), or
b) Multiply x by 2
```
After each operation, we write down the result. If we start with `9`, we can get a sequence such as:
```
[9,3,6,12,4,8] -- 9/3=3 -> 3*2=6 -> 6*2=12 -> 12/3=4 -> 4*2=8
```
You will be given a shuffled sequence of integers and your task is to reorder them so that they conform to the above sequence. There will always be an answer. 
```
For the above example:
solve([12,3,9,4,6,8]) = [9,3,6,12,4,8].
```

More examples in the test cases. Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As you know, the most intelligent beings on the Earth are, of course, cows. This conclusion was reached long ago by the Martian aliens, as well as a number of other intelligent civilizations from outer space. 

Sometimes cows gather into cowavans. This seems to be seasonal. But at this time the cows become passive and react poorly to external stimuli. A cowavan is a perfect target for the Martian scientific saucer, it's time for large-scale abductions, or, as the Martians say, raids. Simply put, a cowavan is a set of cows in a row. 

If we number all cows in the cowavan with positive integers from 1 to n, then we can formalize the popular model of abduction, known as the (a, b)-Cowavan Raid: first they steal a cow number a, then number a + b, then — number a + 2·b, and so on, until the number of an abducted cow exceeds n. During one raid the cows are not renumbered. 

The aliens would be happy to place all the cows on board of their hospitable ship, but unfortunately, the amount of cargo space is very, very limited. The researchers, knowing the mass of each cow in the cowavan, made p scenarios of the (a, b)-raid. Now they want to identify the following thing for each scenario individually: what total mass of pure beef will get on board of the ship. All the scenarios are independent, in the process of performing the calculations the cows are not being stolen. 

<image>

Input

The first line contains the only positive integer n (1 ≤ n ≤ 3·105) — the number of cows in the cowavan.

The second number contains n positive integer wi, separated by spaces, where the i-th number describes the mass of the i-th cow in the cowavan (1 ≤ wi ≤ 109).

The third line contains the only positive integer p — the number of scenarios of (a, b)-raids (1 ≤ p ≤ 3·105).

Each following line contains integer parameters a and b of the corresponding scenario (1 ≤ a, b ≤ n).

Output

Print for each scenario of the (a, b)-raid the total mass of cows, that can be stolen using only this scenario.

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

Examples

Input

3
1 2 3
2
1 1
1 2


Output

6
4


Input

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


Output

9
3
10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a directed graph with N vertices and M edges, not necessarily simple. The i-th edge is oriented from the vertex a_i to the vertex b_i. Divide this graph into strongly connected components and print them in their topological order.

Constraints

* 1 \leq N \leq 500,000
* 1 \leq M \leq 500,000
* 0 \leq a_i, b_i < N

Input

Input is given from Standard Input in the following format:


N M
a_0 b_0
a_1 b_1
:
a_{M - 1} b_{M - 1}


Output

Print 1+K lines, where K is the number of strongly connected components. Print K on the first line. Print the information of each strongly connected component in next K lines in the following format, where l is the number of vertices in the strongly connected component and v_i is the index of the vertex in it.


l v_0 v_1 ... v_{l-1}


Here, for each edge (a_i, b_i), b_i should not appear in earlier line than a_i.

If there are multiple correct output, print any of them.

Example

Input

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


Output

4
1 5
2 4 1
1 2
2 3 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has N subordinates. In order to complete a very important order he will choose exactly K of them. He can't choose less than K since it will be not enough to complete the order in time. On the other hand if he chooses more than K subordinates he can't control them during the operation. Help him to find the number of ways he can choose the team to complete this very important order.

-----Input-----
The first line contains a single positive integer T <= 100, the number of test cases. T test cases follow. The only line of each test case contains two integers N and K, where 0 <= N, K < 2^64. It is guaranteed that the answer will be less than 2^64.

-----Output-----
For each test case, output a single line containing the number of ways to choose the required team.

-----Example-----
Input:
3
2 1
3 3
10 5

Output:
2
1
252

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We define $\mbox{P}$ to be a permutation of the first $n$ natural numbers in the range $[1,n]$. Let $p o s[i]$ denote the value at position $\boldsymbol{i}$ in permutation $\mbox{P}$ using $1$-based indexing. 

$\mbox{P}$ is considered to be an absolute permutation if  $|pos[i]-i|=k$ holds true for every $i\in[1,n]$.

Given $n$ and $\boldsymbol{\mbox{k}}$, print the lexicographically smallest absolute permutation $\mbox{P}$.  If no absolute permutation exists, print -1.

Example 

$n=4$ 

$k=2$   

Create an array of elements from $1$ to $n$, $pos=[1,2,3,4]$.  Using $1$ based indexing, create a permutation where every $|pos[i]-i|=k$.  It can be rearranged to $[3,4,1,2]$ so that all of the absolute differences equal $k=2$:  

pos[i]  i   |pos[i] - i|
  3     1        2
  4     2        2
  1     3        2
  2     4        2

Function Description  

Complete the absolutePermutation function in the editor below.  

absolutePermutation has the following parameter(s):  

int n: the upper bound of natural numbers to consider, inclusive  
int k: the absolute difference between each element's value and its index  

Returns   

int[n]: the lexicographically smallest permutation, or $\left[{-1}\right]$ if there is none   

Input Format

The first line contains an integer $\boldsymbol{\boldsymbol{t}}$, the number of queries. 

Each of the next $\boldsymbol{\boldsymbol{t}}$ lines contains $2$ space-separated integers, $n$ and $\boldsymbol{\mbox{k}}$.  

Constraints

$1\leq t\leq10$
$1\leq n\leq10^5$
$0\leq k<n$

Sample Input
STDIN   Function
-----   --------
3       t = 3 (number of queries)
2 1     n = 2, k = 1
3 0     n = 3, k = 0
3 2     n = 3, k = 2

Sample Output
2 1
1 2 3
-1

Explanation

Test Case 0:

Test Case 1:

Test Case 2: 

No absolute permutation exists, so we print -1 on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lucy is making her road bike ready for the season. All parts have been checked for wear and tear and washed clean and she is ready to put the beauty back together again. There is only one thing troubling her. During the winter she has been to several motivational talks by previous professional cyclists. They have all talked about the importance of correct cadence while cycling. The cadence is the frequency your feet are pedaling at when you are cycling. Lucy is now wondering if she should change her gears setup before she reassembles the bike and goes on her first ride for the year.

Bike gears typically consist of a set of different-sized gears on the crank (the thing connected to the pedals) and a set of different-sized gears on the back wheel. These are connected by the chain to drive the bike forward. Can you help her figure out if she can keep her current setup and still change to all gears without it affecting her cadence too much? Specifically she does not want her cadence to be increased by more than $P$% when changing to the next lighter gear. We assume that the bicycle will continue at the same speed immediately after the gear change.

-----Input-----
The first line of the input consists of three integers $N$, $M$ and $P$ representing the number of gears on the crank, the numbers of gears on the back wheel, and the maximum cadence change in percentage Lucy will tolerate when changing gears.

 Then follows a line with $N$ integers $C_ i$ each representing the number of teeth on each of the gears on the crank.

 Then follows a line with $M$ integers $D_ j$ each representing the number of teeth on each of the gears on the back wheel.



-----Output-----
Output a single line with the text Ride on! if Lucy can change through all the gears from heaviest to lightest in her current setup and Time to change gears! if she cannot.

-----Limits-----
 - $1 \leq N, M \leq 100$
 - $0 \leq P \leq 1000$
 - $3 \leq C, D \leq 100000$

-----Examples-----
Sample Input:
2 11 15
50 34
11 12 13 14 16 18 20 22 25 28 32
Sample Output:
Ride on!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two integers, $m$ and ${k}}$, Alice loves to calculate their power sum using the following formula:
$\textit{PowerSum}(m,k)\equiv\sum\limits_{i=1}^m i^k$

Bob has a set, ${s}$, of $n$ distinct pairwise coprime integers. Bob hates multiples of these integers, so he subtracts ${i}^{k}$ from Alice's power sum for each ${i} \in [1,m]$ whenever there exists at least one $j\in[1,n]$ such that $i\:{mod}\:s_j\equiv0$.

Alice and Bob are now confused about the final value of the power sum and decide to turn to Eve for help. Can you write a program that helps Eve solve this problem? Given ${q}$ queries consisting of $n$, $m$, and ${k}}$, print the value of the power sum modulo $10^9+7$ on a new line for each query.

Input Format

The first line contains an integer, ${q}$, denoting the number of queries. The $2\cdot q$ lines describe each query over two lines:

The first line contains three space-separated integers denoting the respective values of $n$ (the number of integers in Bob's set), ${k}$ (the exponent variable in the power sum formula), and $m$ (the upper range bound in the power sum formula). 
The second line contains $n$ distinct space-separated integers describing the respective elements in set ${s}$. 

Constraints

$1\leq q\leq2$  
$1\leq n\leq50$  
$0\leq k\leq10$  
$1\leq m\leq10^{12}$  
$1\leq s_j\leq10^{12}$     
$s_i\neq s_j,\text{where}\ i\neq j$     
$gcd(s_i,s_j)\equiv1,\text{where}\ i\neq j$  

Output Format

For each query, print the resulting value of the power sum after Bob's subtraction, modulo $10^9+7$.

Sample Input
2
2 1 10
2 3
3 2 18
4 13 9

Sample Output
13
1055

Explanation

We perform the following $q=2$ queries:

Alice first calculates the sum $1^1+2^1+...+10^1=55$. Bob's set contains $2$ and $3$ only, so he subtracts the power of all numbers that are multiples of $2$ and/or $3$ from Alice's sum to get: $55-2^1-3^1-4^1-6^1-8^1-9^1-10^1=13$. We then print the result of $13\:\text{mod}\: (10^9+7)=13$ on a new line.
Alice first calculates the sum $1^2+2^2+...+18^2=2109$. Bob then subtracts multiples of ${4}$, ${9}$, and $13$ from Alice's sum to get: $2109-4^2-8^2-9^2-12^2-13^2-16^2-18^2=1055$. We then print the result of $1055\: \text{mod}\:(10^9+7)=1055$ on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has with him an array A of length N. In one move, he can delete any element from A.

Find the minimum number of deletions Chef must make so that the following condition holds:
Let B denote the resulting array, and M be the length of B.
Then, B_{i} \oplus B_{j} ≤ 1 for every 1 ≤ i, j ≤ M.

Here, \oplus denotes the [bitwise XOR] operation.

For example, [3, 3, 3] and [6, 7, 6, 7] are valid final arrays, while [1, 2] and [6, 7, 8] are not (because 1 \oplus 2 = 3 and 7\oplus 8 = 15, respectively).

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains a single integer N, denoting the length of array A.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} — the elements of array A.

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

For each test case, output on a new line the answer: the minimum number of deletions required so that the given condition is satisfied.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 3\cdot 10^{5}$
$0 ≤ A_{i} ≤ N$
- The sum of $N$ over all test cases won't exceed $3\cdot 10^{5}$.

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

----- Sample Output 1 ------ 
0
2
3
3

----- explanation 1 ------ 
Test case $1$: The given array already satisfies the condition, no deletions need to be done.

Test case $2$: Chef can delete both the $3$'s to make the array $[4, 4, 4]$, which satisfies the condition.

Test case $3$: Chef can use three moves as follows:
- Delete the $1$, the array is now $[2, 3, 4, 0]$.
- Delete the $4$, the array is now $[2, 3, 0]$.
- Delete the $0$, the array is now $[2, 3]$ which satisfies the condition.

It can be verified that using two or less deletions cannot give an array that satisfies the condition.

Test case $4$: Chef must either delete all the $5$'s or all the $6$'s.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sereja has a string A consisting of n lower case English letters.


Sereja calls two strings X and Y each of length n similar if they can be made equal by applying the following operation at most once in each of them.

Chose any two position i, j in the string (i can be equal to j too). Swap the characters at position i with character at position j.


For example strings "abcd" and "acbd" are similar, strings "ab" and "ab" are similar, but strings "abcde" and "bcdea" are not similar. Note that strings  "abc" and "cab" are also similar, as you can swap 'a' and 'c' in the first string to get "cba" and 'a' and 'b' in the second string to get "cba".


Now Sereja is interested in finding number of ordered pairs of non similar strings X and Y such that they can be constructed from a given string A by permutation of its characters. As answer could be large, please output your answer modulo  (10^9 + 7).


Note 
A string s (of size n) is said to be constructed from string t (also of size n) by permutation of its characters if there exists a permutation P (of length n), such that s[i] = t[P[i]] for each i from 1 to n.


Input

First line contain integer T - number of test cases. 
For each of the next T lines:

Each line contains a string A as defined in the problem.



Output
For each test case, output answer modulo 1000000007 (10^9 + 7) in separate line. 

Constraints

1 ≤ T ≤  10 
1 ≤ n ≤  10^5 


Constraints

Example
Input:
2
z
abcd

Output:
0
144

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
During quarantine chef’s friend invented a game. In this game there are two players, player 1 and Player 2. In center of garden there is one finish circle and both players are at different distances respectively $X$ and $Y$ from finish circle.
Between finish circle and Player 1 there are $X$ number of circles and between finish circle and Player 2 there are $Y$ number of circles. Both player wants to reach finish circle with minimum number of jumps. Player can jump one circle to another circle.
Both players can skip $2^0-1$ or $2^1- 1$ or …. or $2^N-1$ circles per jump. A player cannot skip same number of circles in a match more than once. If both players uses optimal way to reach finish circle what will be the difference of minimum jumps needed to reach finish circle by both players. 
If both players reach finish circle with same number of jumps answer will be $0$ $0$.

-----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 2 space separated integers $X$ and $Y$.

-----Output:-----
For each test case, print a single line containing 2 space-separated integers which player win and what is the difference between number of minimum jump required by both players to reach finish circle.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq X,Y \leq 2*10^7$

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

-----Sample Output:-----
0 0
1 1

-----Explanation:-----
Test Case 1:

Test Case 2:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Section numbers are strings of dot-separated integers. The highest level sections (chapters) are numbered 1, 2, 3, etc. Second level sections are numbered 1.1, 1.2, 1.3, 2.1, 2.2, 2.3, etc. Next level sections are numbered 1.1.1, 1.1.2, 1.1.2, 1.2.1, 1.2.2, erc. There is no bound on the number of sections a document may have, nor is there any bound on the number of levels. 

A section of a certain level may appear directly inside a section several levels higher without the levels between. For example, section 1.0.1 may appear directly under section 1, without there being any level 2 section. Section 1.1 comes after section 1.0.1. Sections with trailing ".0" are considered to be the same as the section with the trailing ".0" truncated. Thus, section 1.0 is the same as section 1, and section 1.2.0.0 is the same as section 1.2. 

```if:python
Write a function `compare(section1, section2)` that returns `-1`, `0`, or `1` depending on whether `section1` is before, same as, or after `section2` respectively.
```
```if:javascript
Write a function `cmp(section1, section2)` that returns `-1`, `0`, or `1` depending on whether `section1` is before, same as, or after `section2` respectively.
```
```if:haskell
Write a function `cmp section1 section2` that returns `LT`, `EQ` or `GT` depending on whether `section1` is before, same as, or after `section2` respectively.
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shivam is the youngest programmer in the world, he is just 12 years old. Shivam is learning programming and today he is writing his first program. 

Program is very simple, Given two integers A and B, write a program to add these two numbers.

-----Input-----

The first line contains an integer T, the total number of test cases. Then follow T lines, each line contains two Integers A and B. 

-----Output-----
For each test case, add A and B and display it in a new line.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 0 ≤ A,B ≤ 10000

-----Example-----
Input
3 
1 2
100 200
10 40

Output
3
300
50

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Karl likes Codeforces and subsequences. He wants to find a string of lowercase English letters that contains at least $k$ subsequences codeforces. Out of all possible strings, Karl wants to find a shortest one.

Formally, a codeforces subsequence of a string $s$ is a subset of ten characters of $s$ that read codeforces from left to right. For example, codeforces contains codeforces a single time, while codeforcesisawesome contains codeforces four times: codeforcesisawesome, codeforcesisawesome, codeforcesisawesome, codeforcesisawesome.

Help Karl find any shortest string that contains at least $k$ codeforces subsequences.


-----Input-----

The only line contains a single integer $k$ ($1 \leq k \leq 10^{16})$.


-----Output-----

Print a shortest string of lowercase English letters that contains at least $k$ codeforces subsequences. If there are several such strings, print any of them.


-----Examples-----
Input
1

Output
codeforces

Input
3

Output
codeforcesss

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