vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
-----Problem Statement-----
Chef studies combinatorics. He tries to group objects by their rang (a positive integer associated with each object). He also gives the formula for calculating the number of different objects with rang N as following:

the number of different objects with rang N = F(N) = A0 + A1 * N + A2 * N2 + A3 * N3.

Now Chef wants to know how many different multisets of these objects exist such that sum of rangs of the objects in the multiset equals to S. You are given the coefficients in F(N) and the target sum S. Please, find the number of different multisets modulo 1,000,000,007.

You should consider a multiset as an unordered sequence of integers. Two multisets are different if and only if there at least exists one element which occurs X times in the first multiset but Y times in the second one, where (X ≠ Y).

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. 

The first line of each test case contains four integers A0, A1, A2, A3. The second line contains an integer S.

-----Output-----
For each test case, output a single line containing a single integer - the answer to the test case modulo 1,000,000,007.

-----Constraints-----
- 1 ≤ T ≤ 500
- 1 ≤ S ≤ 100
- 0 ≤ Ai ≤ 1000
- Sum of all S for all test cases is not greater than 500. It's guaranteed that at least one Ai is non-zero.

-----Example-----
Input:
4
1 0 0 0
1
1 0 0 0
3
0 1 0 0
2
2 3 1 4
10

Output:
1
3
3
213986343

-----Explanation-----
Example case 2. 

In the second example function looks as follows F(N) = 1. So for each rang there is a single object of the rang. To get multiset with sum of rangs equal to 3, you can pick: three objects of rang 1, or one object of rang 1 and one of rang 2, or only one object of rang 3. 
Example case 3. 

In the third example function looks as follows F(N) = N. So, you have one distinct object of rang 1, two distinct objects of rang 2, three distinct objects of rang 3 and so on. To get
multiset with sum of rangs equal to 2, you can pick: two objects of rang 1, one of objects of rang 2 (two ways).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Oleg writes down the history of the days he lived. For each day he decides if it was good or bad. Oleg calls a non-empty sequence of days a zebra, if it starts with a bad day, ends with a bad day, and good and bad days are alternating in it. Let us denote bad days as 0 and good days as 1. Then, for example, sequences of days 0, 010, 01010 are zebras, while sequences 1, 0110, 0101 are not.

Oleg tells you the story of days he lived in chronological order in form of string consisting of 0 and 1. Now you are interested if it is possible to divide Oleg's life history into several subsequences, each of which is a zebra, and the way it can be done. Each day must belong to exactly one of the subsequences. For each of the subsequences, days forming it must be ordered chronologically. Note that subsequence does not have to be a group of consecutive days. 

Input

In the only line of input data there is a non-empty string s consisting of characters 0 and 1, which describes the history of Oleg's life. Its length (denoted as |s|) does not exceed 200 000 characters.

Output

If there is a way to divide history into zebra subsequences, in the first line of output you should print an integer k (1 ≤ k ≤ |s|), the resulting number of subsequences. In the i-th of following k lines first print the integer li (1 ≤ li ≤ |s|), which is the length of the i-th subsequence, and then li indices of days forming the subsequence. Indices must follow in ascending order. Days are numbered starting from 1. Each index from 1 to n must belong to exactly one subsequence. If there is no way to divide day history into zebra subsequences, print -1.

Subsequences may be printed in any order. If there are several solutions, you may print any of them. You do not have to minimize nor maximize the value of k.

Examples

Input

0010100


Output

3
3 1 3 4
3 2 5 6
1 7


Input

111


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This night wasn't easy on Vasya. His favorite team lost, and he didn't find himself victorious either — although he played perfectly, his teammates let him down every time. He had to win at least one more time, but the losestreak only grew longer and longer... It's no wonder he didn't get any sleep this night at all.

In the morning, Vasya was waiting the bus to the university on the bus stop. Vasya's thoughts were hazy and so he couldn't remember the right bus' number quite right and got onto the bus with the number $n$.

In the bus, Vasya thought that he could get the order of the digits in the number of the bus wrong. Futhermore, he could "see" some digits several times, but the digits he saw were definitely in the real number of the bus. For example, if Vasya saw the number 2028, it could mean that the real bus number could be 2028, 8022, 2820 or just 820. However, numbers 80, 22208, 52 definitely couldn't be the number of the bus. Also, real bus number couldn't start with the digit 0, this meaning that, for example, number 082 couldn't be the real bus number too.

Given $n$, determine the total number of possible bus number variants.


-----Input-----

The first line contains one integer $n$ ($1 \leq n \leq 10^{18}$) — the number of the bus that was seen by Vasya. It is guaranteed that this number does not start with $0$.


-----Output-----

Output a single integer — the amount of possible variants of the real bus number.


-----Examples-----
Input
97

Output
2

Input
2028

Output
13



-----Note-----

In the first sample, only variants $97$ and $79$ are possible.

In the second sample, the variants (in the increasing order) are the following: $208$, $280$, $802$, $820$, $2028$, $2082$, $2208$, $2280$, $2802$, $2820$, $8022$, $8202$, $8220$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
New AtCoder City has an infinite grid of streets, as follows:

* At the center of the city stands a clock tower. Let (0, 0) be the coordinates of this point.
* A straight street, which we will call East-West Main Street, runs east-west and passes the clock tower. It corresponds to the x-axis in the two-dimensional coordinate plane.
* There are also other infinitely many streets parallel to East-West Main Street, with a distance of 1 between them. They correspond to the lines \ldots, y = -2, y = -1, y = 1, y = 2, \ldots in the two-dimensional coordinate plane.
* A straight street, which we will call North-South Main Street, runs north-south and passes the clock tower. It corresponds to the y-axis in the two-dimensional coordinate plane.
* There are also other infinitely many streets parallel to North-South Main Street, with a distance of 1 between them. They correspond to the lines \ldots, x = -2, x = -1, x = 1, x = 2, \ldots in the two-dimensional coordinate plane.



There are N residential areas in New AtCoder City. The i-th area is located at the intersection with the coordinates (X_i, Y_i) and has a population of P_i. Each citizen in the city lives in one of these areas.

The city currently has only two railroads, stretching infinitely, one along East-West Main Street and the other along North-South Main Street.
M-kun, the mayor, thinks that they are not enough for the commuters, so he decides to choose K streets and build a railroad stretching infinitely along each of those streets.

Let the walking distance of each citizen be the distance from his/her residential area to the nearest railroad.
M-kun wants to build railroads so that the sum of the walking distances of all citizens, S, is minimized.

For each K = 0, 1, 2, \dots, N, what is the minimum possible value of S after building railroads?

Constraints

* 1 \leq N \leq 15
* -10 \ 000 \leq X_i \leq 10 \ 000
* -10 \ 000 \leq Y_i \leq 10 \ 000
* 1 \leq P_i \leq 1 \ 000 \ 000
* The locations of the N residential areas, (X_i, Y_i), are all distinct.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
X_1 Y_1 P_1
X_2 Y_2 P_2
:  :  :
X_N Y_N P_N


Output

Print the answer in N+1 lines.
The i-th line (i = 1, \ldots, N+1) should contain the minimum possible value of S after building railroads for the case K = i-1.

Examples

Input

3
1 2 300
3 3 600
1 4 800


Output

2900
900
0
0


Input

5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400


Output

13800
1600
0
0
0
0


Input

6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200


Output

26700
13900
3200
1200
0
0
0


Input

8
2 2 286017
3 1 262355
2 -2 213815
1 -3 224435
-2 -2 136860
-3 -1 239338
-2 2 217647
-1 3 141903


Output

2576709
1569381
868031
605676
366338
141903
0
0
0

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Recently Bob invented a new game with a tree (we should remind you, that a tree is a connected graph without cycles): he deletes any (possibly, zero) amount of edges of the tree, and counts the product of sizes of the connected components left after the deletion. Your task is to find out the maximum number that Bob can get in his new game for a given tree.

Input Specification:
The first input line contains integer number *n* (1<=≤<=*n*<=≤<=700) — amount of vertices in the tree. The following *n*<=-<=1 lines contain the description of the edges. Each line contains the pair of vertices' indexes, joined by an edge, *a**i*, *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*). It's guaranteed that the graph described in the input is a tree.

Output Specification:
Output the only number — the maximum product of sizes of the connected components, that Bob can get after deleting some of the tree's edges.

Demo Input:
['5\n1 2\n2 3\n3 4\n4 5\n', '8\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7\n6 8\n', '3\n1 2\n1 3\n']

Demo Output:
['6', '18', '3']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string composed of both lowercase and uppercase letters. Sort it in such a manner such that the uppercase and lowercase letter comes in an alternate manner but in sorted way.
Example 1:
Input:
S = bAwutndekWEdkd
Output: AbEdWddekkntuw
Explanation: letters A,E,W are sorted 
as well as letters b,d,d,d,e,k,k,n,t,u,w are 
sorted and both appears alternately in the 
string as far as possible.
Ã¢â¬â¹Example 2:
Input: 
S = AiBFR
Output: AiBFR
Explanation: letters A,B,F,R and sorted 
as well as letter i. 
User Task:
You don't need to read input or print anything. You just have to complete the function stringSort () which takes a string as input and returns the sorted string as described in the problem description.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1). 
Constraints:
1<=|S|<=1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array nums of n elements and q queries . Each query consists of two integers l and r . You task is to find the number of elements of nums[] in range [l,r] which occur atleast k times.
 
Example 1:
Input: nums = {1,1,2,1,3}, Queries = {{1,5},
{2,4}}, k = 1
Output: {3,2}
Explanation: For the 1st query, from l=1 to r=5
1, 2 and 3 have the frequency atleast 1.
For the second query, from l=2 to r=4, 1 and 2 have 
the frequency atleast 1.
 
Example 1:
Input: nums = {1,2,3,1}, Queries = {{1,4},
{2,4},{4,4}, k = 2
Output: {1,0,0}
Explanation: For the 1st query, from l=1 to r=4
1 have the frequency atleast 2.
For the second query, from l=2 to r=4, no number has 
the frequency atleast 2.
For the third query, from l=4 to r=4, no number has 
the frequency atleast 2.
 
Your Task:
Your task is to complete the function solveQueries() which takes nums, Queries and k as input parameter and returns a list containg the answer for each query.
 
Expected Time Complexity: O(n*sqrt(n)*log(n))
Expected Space Compelxity: O(n)
 
Constraints:
1 <= n, no of Queries, k <= 10^{4}
1 <= nums[i] <= 10^{3}
1 <= Queries[i][0] <= Queries[i][1] <= n

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Judging from the previous problem, Friday the 13th really doesn't treat you well, so you start thinking about how to minimize its impact on your life. You are a passionate participant of programming contests, so various competitions are an important part of your schedule. Naturally, you'd like as few of them to be spoiled as possible.

A friendly admin leaked to you the list of dates on which the contests will be held for several years ahead. Check how many of them happen to take place on Friday the 13th of any month.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 10) — the number of the contests you have been told about. The following n lines contain dates of these contests, one per line, formatted as "YYYY-MM-DD" (1974  ≤  YYYY ≤  2030; 01  ≤  MM ≤  12; 01  ≤  DD ≤  31). It's guarateed that all the given dates are correct. Two distinct contests may be at the same day.

Output

Output a single integer — the number of dates which happen to be Friday the 13th.

Examples

Input

5
2012-01-13
2012-09-13
2012-11-20
2013-09-13
2013-09-20


Output

2

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Leha like all kinds of strange things. Recently he liked the function *F*(*n*,<=*k*). Consider all possible *k*-element subsets of the set [1,<=2,<=...,<=*n*]. For subset find minimal element in it. *F*(*n*,<=*k*) — mathematical expectation of the minimal element among all *k*-element subsets.

But only function does not interest him. He wants to do interesting things with it. Mom brought him two arrays *A* and *B*, each consists of *m* integers. For all *i*,<=*j* such that 1<=≤<=*i*,<=*j*<=≤<=*m* the condition *A**i*<=≥<=*B**j* holds. Help Leha rearrange the numbers in the array *A* so that the sum  is maximally possible, where *A*' is already rearranged array.

Input Specification:
First line of input data contains single integer *m* (1<=≤<=*m*<=≤<=2·105) — length of arrays *A* and *B*.

Next line contains *m* integers *a*1,<=*a*2,<=...,<=*a**m* (1<=≤<=*a**i*<=≤<=109) — array *A*.

Next line contains *m* integers *b*1,<=*b*2,<=...,<=*b**m* (1<=≤<=*b**i*<=≤<=109) — array *B*.

Output Specification:
Output *m* integers *a*'1,<=*a*'2,<=...,<=*a*'*m* — array *A*' which is permutation of the array *A*.

Demo Input:
['5\n7 3 5 3 4\n2 1 3 2 3\n', '7\n4 6 5 8 8 2 6\n2 1 2 2 1 1 2\n']

Demo Output:
['4 7 3 5 3\n', '2 6 4 5 8 8 6\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Its Roy's birthday and he is decorating his house with balloons.
He has 26 different types of balloons. They are represented by [a-z].  

Now Roy does not want to have few particular balloons together. Actually he doesn't want to keep any of the two vowel (i.e [a,e,i,o,u] ) balloons together.
So, in one arrangement no two vowels should be together. Given the string of balloons there can be many such arrangements possible.
Help Roy in finding the number of possible arrangements.  

Number of such arrangements can be quite large, so print it modulo 1000000007 (10^9 + 7)  
Also, there's a chance that no such arrangement is possible. Print "-1" in such cases (without quotes)  

Input: 
First line contains T, number of test cases.
Each of next T lines contains a string composed of lower case letters representing all the balloons.  

Output:
For each test case print the required answer.

Constraints:
1 ≤ T ≤ 100
1 ≤ Length of string ≤ 1000000   (10^6)

Note: Sum of string lengths over all the test cases in one file does not exceed 1000000 (10^6)

SAMPLE INPUT
2
abe
ae

SAMPLE OUTPUT
2
-1

Explanation

Test #1: Possible arrangements are
[1] abe
[2] eba

Test #2: There are no any arrangements possible such that any two vowels are not together. So print -1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a pyramid made up of blocks. Each layer of the pyramid is a rectangle of blocks, and the dimensions of these rectangles increment as you descend the pyramid. So, if a layer is a `3x6` rectangle of blocks, then the next layer will be a `4x7` rectangle of blocks. A `1x10` layer will be on top of a `2x11` layer on top of a `3x12` layer, and so on.

## Task

Given the dimensions of a pyramid's topmost layer `w,l`, and its height `h` (aka the number of layers), return the total number of blocks in the pyramid.

## Examples

`num_blocks(1, 1, 2)` will return `5`. This pyramid starts with a `1x1` layer and has 2 layers total. So, there is 1 block in the first layer, and `2x2=4` blocks in the second. Thus, 5 is the total number of blocks.

`num_blocks(2, 4, 3)` will return `47`. This pyramid has 3 layers: `2x4`, `3x5`, and `4x6`. So, there are `47` blocks total.

## Notes

All parameters will always be postive nonzero integers.

Efficiency is important. There will be:

* 100 'small' cases with `w`, `l`, and `h` below `20`.
* 100 'big' cases with `w`, `l`, and `h` between `1e9` and `1e10`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The positive odd numbers are sorted in ascending order as $1,3,5,7,9,11,13,15,17,19\ldots$, and grouped as $(1),(3,5),(7,9,11),(13,15,17,19),...$ and so on.

Thus, the first group is $\left(1\right)$, the second group is $(3,5)$, the third group is $(7,9,11)$, etc. In general, the $k^{\text{th}}$ group contains the next $\boldsymbol{\mbox{k}}$ elements of the sequence. 

Given $\boldsymbol{\mbox{k}}$, find the sum of the elements of the $k^{\text{th}}$ group. For example, for $k=3$, the answer is $27$:

Complete the function sumOfGroup with input integer $\boldsymbol{\mbox{k}}$.  Return the sum of the elements of the $\boldsymbol{\mbox{k}}$th group.

Constraints

$1\leq k\leq10^6$  

Subtasks  

For $50\%$ of the maximum score, $k\leq10^3$  

Sample Input

$k=3$

Sample Output

$27$

Explanation

We have $k=3$. The $3$rd group is $(7,9,11)$ and the sum of its elements is $7+9+11=27$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While walking down the street Vanya saw a label "Hide&Seek". Because he is a programmer, he used & as a bitwise AND for these two words represented as a integers in base 64 and got new word. Now Vanya thinks of some string s and wants to know the number of pairs of words of length |s| (length of s), such that their bitwise AND is equal to s. As this number can be large, output it modulo 10^9 + 7.

To represent the string as a number in numeral system with base 64 Vanya uses the following rules:  digits from '0' to '9' correspond to integers from 0 to 9;  letters from 'A' to 'Z' correspond to integers from 10 to 35;  letters from 'a' to 'z' correspond to integers from 36 to 61;  letter '-' correspond to integer 62;  letter '_' correspond to integer 63. 


-----Input-----

The only line of the input contains a single word s (1 ≤ |s| ≤ 100 000), consisting of digits, lowercase and uppercase English letters, characters '-' and '_'.


-----Output-----

Print a single integer — the number of possible pairs of words, such that their bitwise AND is equal to string s modulo 10^9 + 7.


-----Examples-----
Input
z

Output
3

Input
V_V

Output
9

Input
Codeforces

Output
130653412



-----Note-----

For a detailed definition of bitwise AND we recommend to take a look in the corresponding article in Wikipedia.

In the first sample, there are 3 possible solutions:   z&_ = 61&63 = 61 = z  _&z = 63&61 = 61 = z  z&z = 61&61 = 61 = z

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Dima and Trap Graph

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Dima and Inna love spending time together. The problem is, Seryozha isn't too enthusiastic to leave his room for some reason. But Dima and Inna love each other so much that they decided to get criminal...

Dima constructed a trap graph. He shouted: "Hey Seryozha, have a look at my cool graph!" to get his roommate interested and kicked him into the first node.

A trap graph is an undirected graph consisting of *n* nodes and *m* edges. For edge number *k*, Dima denoted a range of integers from *l**k* to *r**k* (*l**k*<=≤<=*r**k*). In order to get out of the trap graph, Seryozha initially (before starting his movements) should pick some integer (let's call it *x*), then Seryozha must go some way from the starting node with number 1 to the final node with number *n*. At that, Seryozha can go along edge *k* only if *l**k*<=≤<=*x*<=≤<=*r**k*.

Seryozha is a mathematician. He defined the loyalty of some path from the 1-st node to the *n*-th one as the number of integers *x*, such that if he initially chooses one of them, he passes the whole path. Help Seryozha find the path of maximum loyalty and return to his room as quickly as possible!

Input Specification:
The first line of the input contains two integers *n* and *m* (2<=≤<=*n*<=≤<=103,<=0<=≤<=*m*<=≤<=3·103). Then follow *m* lines describing the edges. Each line contains four integers *a**k*, *b**k*, *l**k* and *r**k* (1<=≤<=*a**k*,<=*b**k*<=≤<=*n*,<=1<=≤<=*l**k*<=≤<=*r**k*<=≤<=106). The numbers mean that in the trap graph the *k*-th edge connects nodes *a**k* and *b**k*, this edge corresponds to the range of integers from *l**k* to *r**k*.

Note that the given graph can have loops and multiple edges.

Output Specification:
In a single line of the output print an integer — the maximum loyalty among all paths from the first node to the *n*-th one. If such paths do not exist or the maximum loyalty equals 0, print in a single line "Nice work, Dima!" without the quotes.

Demo Input:
['4 4\n1 2 1 10\n2 4 3 5\n1 3 1 5\n2 4 2 7\n', '5 6\n1 2 1 10\n2 5 11 20\n1 4 2 5\n1 3 10 11\n3 4 12 10000\n4 5 6 6\n']

Demo Output:
['6\n', 'Nice work, Dima!\n']

Note:
Explanation of the first example.

Overall, we have 2 ways to get from node 1 to node 4: first you must go along the edge 1-2 with range [1-10], then along one of the two edges 2-4. 

One of them contains range [3-5], that is, we can pass through with numbers 3, 4, 5. So the loyalty of such path is 3.

If we go along edge 2-4 with range [2-7], then we can pass through with numbers 2, 3, 4, 5, 6, 7. The loyalty is 6. That is the answer.

The edge 1-2 have no influence on the answer because its range includes both ranges of the following edges.

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