vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Lisa just got a new math workbook.  A workbook contains exercise problems, grouped into chapters.  Lisa believes a problem to be special if its index (within a chapter) is the same as the page number where it's located.  The format of Lisa's book is as follows:

There are $n$ chapters in Lisa's workbook, numbered from $\mbox{1}$ to $n$.
The $i^{\mbox{th}}$ chapter has $arr\left[i\right]$ problems, numbered from $\mbox{1}$ to $arr\left[i\right]$.
Each page can hold up to $\boldsymbol{\mbox{k}}$ problems. Only a chapter's last page of exercises may contain fewer than $\boldsymbol{\mbox{k}}$ problems.
Each new chapter starts on a new page, so a page will never contain problems from more than one chapter.
The page number indexing starts at $\mbox{1}$.

Given the details for Lisa's workbook, can you count its number of special problems?

Example 

$arr=[4,2]$ 

$k=3$   

Lisa's workbook contains $ar r[1]=4$ problems for chapter $\mbox{1}$, and $arr[2]=2$ problems for chapter $2$.  Each page can hold $k=3$ problems.  

The first page will hold $3$ problems for chapter $\mbox{1}$.  Problem $\mbox{1}$ is on page $\mbox{1}$, so it is special.  Page $2$ contains only Chapter $\mbox{1}$, Problem $\begin{array}{c}4\end{array}$, so no special problem is on page $2$.  Chapter $2$ problems start on page $3$ and there are $2$ problems.  Since there is no problem $3$ on page $3$, there is no special problem on that page either.  There is $\mbox{1}$ special problem in her workbook.

Note: See the diagram in the Explanation section for more details.  

Function Description  

Complete the workbook function in the editor below.     

workbook has the following parameter(s):  

int n: the number of chapters       
int k: the maximum number of problems per page  
int arr[n]: the number of problems in each chapter  

Returns 

- int: the number of special problems in the workbook   

Input Format

The first line contains two integers $n$ and $\boldsymbol{\mbox{k}}$, the number of chapters and the maximum number of problems per page. 

The second line contains $n$ space-separated integers $arr\left[i\right]$ where $arr\left[i\right]$ denotes the number of problems in the $i^{\mbox{th}}$ chapter.

Constraints

$1\leq n,k,ar r[i]\leq100$

Sample Input
STDIN       Function
-----       --------
5 3         n = 5, k = 3
4 2 6 1 10  arr = [4, 2, 6, 1, 10]

Sample Output
4

Explanation

The diagram below depicts Lisa's workbook with $n=5$ chapters and a maximum of $k=3$ problems per page. Special problems are outlined in red, and page numbers are in yellow squares.

There are $\begin{array}{c}4\end{array}$ special problems and thus we print the number $\begin{array}{c}4\end{array}$ on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions is constraints.

There are $n$ kids, each of them is reading a unique book. At the end of any day, the $i$-th kid will give his book to the $p_i$-th kid (in case of $i = p_i$ the kid will give his book to himself). It is guaranteed that all values of $p_i$ are distinct integers from $1$ to $n$ (i.e. $p$ is a permutation). The sequence $p$ doesn't change from day to day, it is fixed.

For example, if $n=6$ and $p=[4, 6, 1, 3, 5, 2]$ then at the end of the first day the book of the $1$-st kid will belong to the $4$-th kid, the $2$-nd kid will belong to the $6$-th kid and so on. At the end of the second day the book of the $1$-st kid will belong to the $3$-th kid, the $2$-nd kid will belong to the $2$-th kid and so on.

Your task is to determine the number of the day the book of the $i$-th child is returned back to him for the first time for every $i$ from $1$ to $n$.

Consider the following example: $p = [5, 1, 2, 4, 3]$. The book of the $1$-st kid will be passed to the following kids:  after the $1$-st day it will belong to the $5$-th kid,  after the $2$-nd day it will belong to the $3$-rd kid,  after the $3$-rd day it will belong to the $2$-nd kid,  after the $4$-th day it will belong to the $1$-st kid. 

So after the fourth day, the book of the first kid will return to its owner. The book of the fourth kid will return to him for the first time after exactly one day.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 1000$) — the number of queries. Then $q$ queries follow.

The first line of the query contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of kids in the query. The second line of the query contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, all $p_i$ are distinct, i.e. $p$ is a permutation), where $p_i$ is the kid which will get the book of the $i$-th kid.

It is guaranteed that $\sum n \le 2 \cdot 10^5$ (sum of $n$ over all queries does not exceed $2 \cdot 10^5$).


-----Output-----

For each query, print the answer on it: $n$ integers $a_1, a_2, \dots, a_n$, where $a_i$ is the number of the day the book of the $i$-th child is returned back to him for the first time in this query.


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

Output
1 1 1 1 1 
3 3 3 
2 3 3 2 1 3 
1 
2 2 2 2 
4 4 4 1 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's define `increasing` numbers as the numbers whose digits, read from left to right, are never less than the previous ones: 234559 is an example of increasing number.

Conversely, `decreasing` numbers have all the digits read from left to right so that no digits is bigger than the previous one: 97732 is an example of decreasing number.

You do not need to be the next Gauss to figure that all numbers with 1 or 2 digits are either increasing or decreasing: 00, 01, 02, ..., 98, 99 are all belonging to one of this categories (if not both, like 22 or 55): 101 is indeed the first number which does NOT fall into either of the categories. Same goes for all the numbers up to 109, while 110 is again a decreasing number.

Now your task is rather easy to declare (a bit less to perform): you have to build a function to return the total occurrences of all the increasing or decreasing numbers *below* 10 raised to the xth power (x will always be >= 0).

To give you a starting point, there are a grand total of increasing and decreasing numbers as shown in the table:

|Total  | Below
|---------------
|1      | 1
|10     | 10
|100    | 100
|475    | 1000
|1675   | 10000
|4954   | 100000
|12952  | 1000000

This means that your function will have to behave like this:
```python
total_inc_dec(0)==1
total_inc_dec(1)==10
total_inc_dec(2)==100
total_inc_dec(3)==475
total_inc_dec(4)==1675
total_inc_dec(5)==4954
total_inc_dec(6)==12952
```

**Tips:** efficiency and trying to figure out how it works are essential: with a brute force approach, some tests with larger numbers may take more than the total computing power currently on Earth to be finished in the short allotted time.

To make it even clearer, the increasing or decreasing numbers between in the range 101-200 are: [110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 122, 123, 124, 125, 126, 127, 128, 129, 133, 134, 135, 136, 137, 138, 139, 144, 145, 146, 147, 148, 149, 155, 156, 157, 158, 159, 166, 167, 168, 169, 177, 178, 179, 188, 189, 199, 200], that is 47 of them. In the following range, 201-300, there are 41 of them and so on, getting rarer and rarer.

**Trivia:** just for the sake of your own curiosity, a number which is neither decreasing of increasing is called a `bouncy` number, like, say, 3848 or 37294; also, usually 0 is not considered being increasing, decreasing or bouncy, but it will be for the purpose of this kata

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mehta was doing his usual office work when all of a sudden, he refreshes his Gmail. It contained the mail of his not so old friend who was still jobless and asking Mehta for a certain help. His Friend Verma had applied for a certain hiring challenge for some certain company. So, Verma gave Mehta a link of the contest which contained the following question. So, you being a colleague of Mehta decide to help him with his friend's task.

Task: 
Given three integers A, B and K, you need to report the K^th number between A and B(both inclusive), satisfying the property that: the number does not contain a digit 'zero' and product of digits of number is a perfect square. If there doesn't exist that K^th number output "-1"(without quotes).

Input:
First Line contains the number of test cases T.
Next T lines contain 3 space separated integers A, B, K as mentioned in the task.

Output:
Output T lines as answer for every test case.

Constraints:
1 ≤ T ≤ 100
1 ≤ A ≤ B ≤ 10^18
1 ≤ K ≤ 10^7

SAMPLE INPUT
3
1 10 4
8 14 2
1 1000 23

SAMPLE OUTPUT
-1
11
119

Explanation

Sample Case#1:  {1,4,9} are the only numbers that satisfy above property, so there is no 4th number, hence answer is -1. 
Sample Case#2: {9,11,14} are three numbers in range [8,14] which have product of digits as perfect square, so, 2nd number in range [8,14] will be 11.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A poor old man works in a palace for a living. One day the old man's wife met with an accident. She needed an immediate operation but the old man's savings were not enough for the operation. He went running to the king to beg for money. The king told that he will not only pay the full amount for the operation but also double his salary. But for that the old man had to pass a test. The king showed him a pile of glass plates kept one above another, each one being smaller than the one beneath. The plates were kept in box 1. He had to transfer the plates to box 3 using box 2. However, there were some constraints. The old man could only take one plate at a time and he could only place a smaller plate on top of a larger plate. He could take a plate only from the top. Help the old man do so. There are N plates and he has to tell the nth move in the format (i, j) where a plate is being moved from ith box to jth box.
Note:
Given any number of plates, they can be transferred from box 1 to box 3 using box 2 using the following steps.
Step 1: Transfer first N-1 plates from box 1 to box 2 using box 3.
Step 2: Transfer the remaining plate from box 1 to box 3.
Step 3: Transfer the first N-1 plates from box 2 to box 3 using box 1.
Example 1:
Input: N = 2, n = 2
Output: 1 3
Explaination:  The plate on top of box 1 is 
first transferred to box 2. The second plate 
from box 1 is transferred to box 3 and finally 
the plate from box 2 is transferred to box 3. 
In each situation, all the constraints are 
satisfied. You are required to print the 2nd 
move which is "Move plate from box 1 to box 3", 
hence 1 3.
Example 2:
Input: N = 3, n = 4.
Output: 1 3
Explaination: The movements of plates will 
be from 1 to 3. Then from 1 to 2. Then from 
3 to 2. And finally 4th move from 1 to 3.
Your Task:
You do not need to read input or print anyting. Your task is to complete the function shiftPile() which takes N and n as input parameters and returns the nth move in a list.
Expected Time Complexity: O(2^{N})
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 20
1 ≤ n ≤ 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sam is an avid collector of numbers. Every time he finds a new number he throws it on the top of his number-pile. Help Sam organise his collection so he can take it to the International Number Collectors Conference in Cologne. 

Given an array of numbers, your function should return an array of arrays, where each subarray contains all the duplicates of a particular number. Subarrays should be in the same order as the first occurence of the number they contain:
Assume the input is always going to be an array of numbers. If the input is an empty array, an empty array should be returned.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given array a with n elements and the number m. Consider some subsequence of a and the value of least common multiple (LCM) of its elements. Denote LCM as l. Find any longest subsequence of a with the value l ≤ m.

A subsequence of a is an array we can get by erasing some elements of a. It is allowed to erase zero or all elements.

The LCM of an empty array equals 1.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^6) — the size of the array a and the parameter from the problem statement.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^9) — the elements of a.


-----Output-----

In the first line print two integers l and k_{max} (1 ≤ l ≤ m, 0 ≤ k_{max} ≤ n) — the value of LCM and the number of elements in optimal subsequence.

In the second line print k_{max} integers — the positions of the elements from the optimal subsequence in the ascending order.

Note that you can find and print any subsequence with the maximum length.


-----Examples-----
Input
7 8
6 2 9 2 7 2 3

Output
6 5
1 2 4 6 7

Input
6 4
2 2 2 3 3 3

Output
2 3
1 2 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Anton found a box with digits in his room. There are k_2 digits 2, k_3 digits 3, k_5 digits 5 and k_6 digits 6.

Anton's favorite integers are 32 and 256. He decided to compose this integers from digits he has. He wants to make the sum of these integers as large as possible. Help him solve this task!

Each digit can be used no more than once, i.e. the composed integers should contain no more than k_2 digits 2, k_3 digits 3 and so on. Of course, unused digits are not counted in the sum.


-----Input-----

The only line of the input contains four integers k_2, k_3, k_5 and k_6 — the number of digits 2, 3, 5 and 6 respectively (0 ≤ k_2, k_3, k_5, k_6 ≤ 5·10^6).


-----Output-----

Print one integer — maximum possible sum of Anton's favorite integers that can be composed using digits from the box.


-----Examples-----
Input
5 1 3 4

Output
800

Input
1 1 1 1

Output
256



-----Note-----

In the first sample, there are five digits 2, one digit 3, three digits 5 and four digits 6. Anton can compose three integers 256 and one integer 32 to achieve the value 256 + 256 + 256 + 32 = 800. Note, that there is one unused integer 2 and one unused integer 6. They are not counted in the answer.

In the second sample, the optimal answer is to create on integer 256, thus the answer is 256.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive integer L in base two.
How many pairs of non-negative integers (a, b) satisfy the following conditions?
 - a + b \leq L
 - a + b = a \mbox{ XOR } b
Since there can be extremely many such pairs, print the count modulo 10^9 + 7.
 What is XOR?
The XOR of integers A and B, A \mbox{ XOR } B, is defined as follows:
 - When A \mbox{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.
For example, 3 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ XOR } 101 = 110.)

-----Constraints-----
 - L is given in base two, without leading zeros.
 - 1 \leq L < 2^{100\ 001}

-----Input-----
Input is given from Standard Input in the following format:
L

-----Output-----
Print the number of pairs (a, b) that satisfy the conditions, modulo 10^9 + 7.

-----Sample Input-----
10

-----Sample Output-----
5

Five pairs (a, b) satisfy the conditions: (0, 0), (0, 1), (1, 0), (0, 2) and (2, 0).

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

You are given a positive integer sequence $A$ of length $N$. You can remove any numbers from the sequence to make the sequence “friendly". A sequence is called friendly if there exists an integer $k$ (>1) such that every number in the sequence is a multiple of $k$. Since the empty sequence is friendly, it is guaranteed that you can make the initial sequence friendly.

You noticed that there may be multiple ways to make the sequence friendly. So you decide to maximize the sum of all the numbers in the friendly sequence. Please calculate the maximum sum of the all numbers in the friendly sequence which can be obtained from the initial sequence.

* * *

Input

The input consists of a single test case formatted as follows.

> $N$ $A_1$ $\vdots$ $A_N$

The first line consists of a single integer $N$ ($1 \le N \le 1000$). The $i+1$-st line consists of an integer $A_i$ ($1 \le A_i \le 10^9$ for $1 \le i \le N$).

Output

Print the maximum sum of all the numbers in the friendly sequence which can be obtained from the initial sequence.

Examples

Input| Output
---|---


6
1
2
3
4
5
6


|


12



3
173
1733
111733


|


111733



4
1
1
1
1


|


0



10
999999999
999999999
999999999
999999999
999999999
999999999
999999999
999999999
999999999
999999999


|


9999999990



1
999999999


|


999999999



10
28851
8842
9535
2311
25337
26467
12720
10561
8892
6435


|


56898






Example

Input




Output

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chintu is a final year computer engineering student , who loves programming . All the time he is busy coding . His friends though don't like to code and 
always want to enjoy . They ask their friend Chintu to accompany them on their trip to Goa , but he refuses . They persuade him , so he agrees on one condition
, if they solve the following problem . He asks them to prepare a list of friends going to Goa maintaining the following property  , for the first k+1 friends
the name of ith friend(indexing from 0) , where  0 ≤ i < k, should be a substring of the (i+1)th friend .
Find the number of permutations of all friends which are going on the Trip . 
Since the friends are not that smart, they have asked you to solve it . Please help them .

Note: 
Since the value can be very large take modulo : 10^9 + 9.
All names are lowercase.
All the friends names are distinct. 

Input :
The first line contains T , the number of test cases .
The next line  contains n , the total number of friends and k.
The next n lines contains the names of the friends.

Constraints : 
 1 ≤ T ≤ 100
3 ≤ n ≤30 , 0 ≤ k ≤ 29
Length of each name , L is  2 ≤ L ≤ 30.

output : 
a single integer giving the number of permutations.

SAMPLE INPUT
2
3 1 
raj 
rajunder 
raju 
3  0 
rajat
kashish
piyush

SAMPLE OUTPUT
3
6

Explanation

for the first test case , since k = 1 , we have to maintain the order for only the first and the second i.e. k+1 friends , so the 
possible configurations are 

raj rajunder raju 
raj raju rajunder 
raju rajunder raj
So, output 3 

for the second case , since k = 0, therefore answer is 6 . i.e. all possible configurations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer N. Consider all possible segments on the coordinate axis with endpoints at integer points with coordinates between 0 and N, inclusive; there will be $\frac{n(n + 1)}{2}$ of them.

You want to draw these segments in several layers so that in each layer the segments don't overlap (they might touch at the endpoints though). You can not move the segments to a different location on the coordinate axis. 

Find the minimal number of layers you have to use for the given N.


-----Input-----

The only input line contains a single integer N (1 ≤ N ≤ 100).


-----Output-----

Output a single integer - the minimal number of layers required to draw the segments for the given N.


-----Examples-----
Input
2

Output
2

Input
3

Output
4

Input
4

Output
6



-----Note-----

As an example, here are the segments and their optimal arrangement into layers for N = 4. [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Little Elephant loves permutations of integers from 1 to n very much. But most of all he loves sorting them. To sort a permutation, the Little Elephant repeatedly swaps some elements. As a result, he must receive a permutation 1, 2, 3, ..., n.

This time the Little Elephant has permutation p_1, p_2, ..., p_{n}. Its sorting program needs to make exactly m moves, during the i-th move it swaps elements that are at that moment located at the a_{i}-th and the b_{i}-th positions. But the Little Elephant's sorting program happened to break down and now on every step it can equiprobably either do nothing or swap the required elements.

Now the Little Elephant doesn't even hope that the program will sort the permutation, but he still wonders: if he runs the program and gets some permutation, how much will the result of sorting resemble the sorted one? For that help the Little Elephant find the mathematical expectation of the number of permutation inversions after all moves of the program are completed.

We'll call a pair of integers i, j (1 ≤ i < j ≤ n) an inversion in permutatuon p_1, p_2, ..., p_{n}, if the following inequality holds: p_{i} > p_{j}.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 1000, n > 1) — the permutation size and the number of moves. The second line contains n distinct integers, not exceeding n — the initial permutation. Next m lines each contain two integers: the i-th line contains integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}) — the positions of elements that were changed during the i-th move.


-----Output-----

In the only line print a single real number — the answer to the problem. The answer will be considered correct if its relative or absolute error does not exceed 10^{ - 6}.


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

Output
0.500000000

Input
4 3
1 3 2 4
1 2
2 3
1 4

Output
3.000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Everyone’s favorite character and puppet-maker Geppetto has opened a new pizza place, the best in town. Geppetto is trying to make the best pizza possible, but at the same time he doesn’t want to have a small selection of pizzas.

He makes his pizzas out of $N$ ingredients marked with numbers from $1$ to $N$. All that would be simple if he could mix any ingredient with every ingredient on the pizza, but unfortunately, that is not the case. Sometimes some ingredients cannot mix and that creates additional complications for our pizza master.

There are $M$ pairs of ingredients that cannot be on the same pizza at the same time. Given these restrictions, Geppetto wants to know how many different pizzas he can make. Help him answer this question. Two pizzas are considered different if there is an ingredient of index $i$ that is on one pizza, but not on the other.

-----Input-----
The first line of input contains two integers $N$ and $M$ ($1 \leq N \leq 20$, $0 \leq M \leq 400$). Each of the following $M$ lines contains two different numbers $a$ and $b$, they represent the prohibition of mixing ingredients marked with $a$ and $b$ on the pizza. ($1 \leq a, b\leq N$). All pairs of ingredients are not necessarily distinct, some pair could occur multiple times.

-----Output-----
The first and only line of output must contain the number of different pizzas given the restrictions in the task.

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

Sample Input 2:
3 0
Sample Output 2:
8

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