vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are an experienced investor who is investing in multiple companies. At the end of the year you are expected to file your taxes, which requires you to track and report the total number of shares you held during any of your trading days during the year.

The records you have kept are sorted by company: for each company, you have a list of notes stating how many shares of that company you owned on a given day.

Your tax accountant has asked you to produce a list of the total number of shares across all companies you have held on each of the days on which you have traded and recorded your holdings.

-----Input-----
The first line of input contains an integer $C$ ($1 \le C \le 20$), the total number of companies of which you hold shares. Next will be $C$ blocks of records, one for each company.

Each record block starts with an integer $K$ ($1 \le K \le 50$), which is the number of records you have kept for this company. This is followed by $K$ lines of input, each containing two integers $N$ ($1 \le N \le 1000$) and $D$ ($1 \le D \le 365$), denoting that you held $N$ shares of this company on day $D$. The days in the input may be specified in any order.

-----Output-----
Print, on a single line, for each day for which you have at least one record, the total number of shares held on that day. The share totals shall be printed in increasing order of trading days.

-----Examples-----
Sample Input:
3
2
20 100
100 10
1
150 50
1
150 100
Sample Output:
100 250 320

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A factorial $n!$ of a positive integer $n$ is defined as the product of all positive integers smaller than or equal to $n$. For example,\[ 21! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot 21 = 51090942171709440000. \]

It is straightforward to calculate the factorial of a small integer, and you have probably done it many times before. In this problem, however, your task is reversed. You are given the value of $n!$ and you have to find the value of $n$.

-----Input-----
The input contains the factorial $n!$ of a positive integer $n$. The number of digits of $n!$ is at most $10^{6}$.

-----Output-----
Output the value of $n$.

-----Examples-----
Sample Input 1:
120
Sample Output 1:
5

Sample Input 2:
51090942171709440000
Sample Output 2:
21

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ilya lives in the beautiful city of Bytes lying in a hilly terrain. She loves to ride her bicycle on the hills whenever she gets a chance to do so.

There are check-posts located on the hill at a unit distance from each other. The height of the check posts is given in an array A.
Ilya has to visit her aunt who lives N check-posts away.
Being a hilly area, the terrain in between the check-posts is either monotonically increasing or decreasing. She is initially standing at checkpoint indexed 1.
However, Ilya suffers from a rare sleeping disorder in which she goes to sleep while riding her bicycle if the terrain is uniform. She wakes up whenever there is a change in nature of terrain i.e from increasing to decreasing or from decreasing to increasing.
You have been given an easy task of counting number of times Ilya wakes up during her sleep as she passes through these N check-posts falling on the way to her aunt's house. 

Note

You can safely assume that the terrain between i^th and (i + 1)^th checkpoint will be uniform i.e it will have either increasing slope or decreasing slope.
 
It is guaranteed that no two adjacent check-posts have same heights.
 


 

Input

The first line of the input contains an integer T denoting the number of test cases.
The first line of the test case consists of an integer N denoting the number of check-posts.
The first line of each test case contains a single integer N denoting the number of check-posts. The second line contains N space-separated integers A1, A2, ..., AN denoting the heights of check-posts falling on the way. 

 

Output

For each test case, output a single integer denoting number of times Ilya wakes up from her sleep in a separate line .

 

Constraints

1 ≤ T ≤  10 
2 ≤  N ≤  10^5  
-10^9 ≤  Ai  ≤ 10^9 

 

Example
Input:
2
3
1 3 2
5
1 2 3 4 5 
Output:
1 
0 

Explanation
Example case 1. She wakes up when the height  changes from 3 to 2
Example case 2. She never wakes up in between the sleep

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Vasily the Bear and Beautiful Strings

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasily the Bear loves beautiful strings. String *s* is beautiful if it meets the following criteria: 
 1.  String *s* only consists of characters 0 and 1, at that character 0 must occur in string *s* exactly *n* times, and character 1 must occur exactly *m* times. 1.  We can obtain character *g* from string *s* with some (possibly, zero) number of modifications. The character *g* equals either zero or one. 
A modification of string with length at least two is the following operation: we replace two last characters from the string by exactly one other character. This character equals one if it replaces two zeros, otherwise it equals zero. For example, one modification transforms string "01010" into string "0100", two modifications transform it to "011". It is forbidden to modify a string with length less than two.

Help the Bear, count the number of beautiful strings. As the number of beautiful strings can be rather large, print the remainder after dividing the number by 1000000007 (109<=+<=7).

Input Specification:
The first line of the input contains three space-separated integers *n*,<=*m*,<=*g* (0<=≤<=*n*,<=*m*<=≤<=105,<=*n*<=+<=*m*<=≥<=1,<=0<=≤<=*g*<=≤<=1).

Output Specification:
Print a single integer — the answer to the problem modulo 1000000007 (109<=+<=7).

Demo Input:
['1 1 0\n', '2 2 0\n', '1 1 1\n']

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

Note:
In the first sample the beautiful strings are: "01", "10".

In the second sample the beautiful strings are: "0011", "1001", "1010", "1100".

In the third sample there are no beautiful strings.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fibonacci strings are defined as follows: 

  * f1 = «a» 
  * f2 = «b» 
  * fn = fn - 1 fn - 2, n > 2



Thus, the first five Fibonacci strings are: "a", "b", "ba", "bab", "babba".

You are given a Fibonacci string and m strings si. For each string si, find the number of times it occurs in the given Fibonacci string as a substring.

Input

The first line contains two space-separated integers k and m — the number of a Fibonacci string and the number of queries, correspondingly.

Next m lines contain strings si that correspond to the queries. It is guaranteed that strings si aren't empty and consist only of characters "a" and "b".

The input limitations for getting 30 points are: 

  * 1 ≤ k ≤ 3000
  * 1 ≤ m ≤ 3000
  * The total length of strings si doesn't exceed 3000



The input limitations for getting 100 points are: 

  * 1 ≤ k ≤ 1018
  * 1 ≤ m ≤ 104
  * The total length of strings si doesn't exceed 105



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

Output

For each string si print the number of times it occurs in the given Fibonacci string as a substring. Since the numbers can be large enough, print them modulo 1000000007 (109 + 7). Print the answers for the strings in the order in which they are given in the input.

Examples

Input

6 5
a
b
ab
ba
aba


Output

3
5
3
3
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You helped Dima to have a great weekend, but it's time to work. Naturally, Dima, as all other men who have girlfriends, does everything wrong.

Inna and Dima are now in one room. Inna tells Dima off for everything he does in her presence. After Inna tells him off for something, she goes to another room, walks there in circles muttering about how useless her sweetheart is. During that time Dima has time to peacefully complete k - 1 tasks. Then Inna returns and tells Dima off for the next task he does in her presence and goes to another room again. It continues until Dima is through with his tasks.

Overall, Dima has n tasks to do, each task has a unique number from 1 to n. Dima loves order, so he does tasks consecutively, starting from some task. For example, if Dima has 6 tasks to do in total, then, if he starts from the 5-th task, the order is like that: first Dima does the 5-th task, then the 6-th one, then the 1-st one, then the 2-nd one, then the 3-rd one, then the 4-th one.

Inna tells Dima off (only lovingly and appropriately!) so often and systematically that he's very well learned the power with which she tells him off for each task. Help Dima choose the first task so that in total he gets told off with as little power as possible.


-----Input-----

The first line of the input contains two integers n, k (1 ≤ k ≤ n ≤ 10^5). The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^3), where a_{i} is the power Inna tells Dima off with if she is present in the room while he is doing the i-th task.

It is guaranteed that n is divisible by k.


-----Output-----

In a single line print the number of the task Dima should start with to get told off with as little power as possible. If there are multiple solutions, print the one with the minimum number of the first task to do.


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

Output
1

Input
10 5
1 3 5 7 9 9 4 1 8 5

Output
3



-----Note-----

Explanation of the first example.

If Dima starts from the first task, Inna tells him off with power 3, then Dima can do one more task (as k = 2), then Inna tells him off for the third task with power 1, then she tells him off for the fifth task with power 5. Thus, Dima gets told off with total power 3 + 1 + 5 = 9. If Dima started from the second task, for example, then Inna would tell him off for tasks 2, 4 and 6 with power 2 + 6 + 4 = 12. 

Explanation of the second example.

In the second example k = 5, thus, Dima manages to complete 4 tasks in-between the telling off sessions. Thus, Inna tells Dima off for tasks number 1 and 6 (if he starts from 1 or 6), 2 and 7 (if he starts from 2 or 7) and so on. The optimal answer is to start from task 3 or 8, 3 has a smaller number, so the answer is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given five positive integers, find the minimum and maximum values that can be calculated by summing exactly four of the five integers. Then print the respective minimum and maximum values as a single line of two space-separated long integers.  

Example 

$arr=[1,3,5,7,9]$

The minimum sum is $1+3+5+7=16$ and the maximum sum is $3+5+7+9=24$.  The function prints

16 24

Function Description  

Complete the miniMaxSum function in the editor below.  

miniMaxSum has the following parameter(s):

arr: an array of $5$ integers  

Print   

Print two space-separated integers on one line: the minimum sum and the maximum sum of $4$ of $5$ elements.  

Input Format

A single line of five space-separated integers.

Constraints

$1\leq ar r[i]\leq10^9$  

Output Format

Print two space-separated long integers denoting the respective minimum and maximum values that can be calculated by summing exactly four of the five integers. (The output can be greater than a 32 bit integer.)

Sample Input
1 2 3 4 5

Sample Output
10 14

Explanation

The numbers are $1$, $2$, $3$, $4$, and $5$. Calculate the following sums using four of the five integers:

Sum everything except $1$, the sum is $2+3+4+5=14$.
Sum everything except $2$, the sum is $1+3+4+5=13$.
Sum everything except $3$, the sum is $1+2+4+5=12$.
Sum everything except $4$, the sum is $1+2+3+5=11$.
Sum everything except $5$, the sum is $1+2+3+4=10$.

Hints: Beware of integer overflow! Use 64-bit Integer.

Need help to get started? Try the Solve Me First problem

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a building with 2N floors, numbered 1, 2, \ldots, 2N from bottom to top.
The elevator in this building moved from Floor 1 to Floor 2N just once.
On the way, N persons got on and off the elevator. Each person i (1 \leq i \leq N) got on at Floor A_i and off at Floor B_i. Here, 1 \leq A_i < B_i \leq 2N, and just one person got on or off at each floor.
Additionally, because of their difficult personalities, the following condition was satisfied:
 - Let C_i (= B_i - A_i - 1) be the number of times, while Person i were on the elevator, other persons got on or off. Then, the following holds:
 - If there was a moment when both Person i and Person j were on the elevator, C_i = C_j.
We recorded the sequences A and B, but unfortunately, we have lost some of the records. If the record of A_i or B_i is lost, it will be given to you as -1.
Additionally, the remaining records may be incorrect.
Determine whether there is a pair of A and B that is consistent with the remaining records.

-----Constraints-----
 - 1 \leq N \leq 100
 - A_i = -1 or 1 \leq A_i \leq 2N.
 - B_i = -1 or 1 \leq B_i \leq 2N.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 B_1
A_2 B_2
:
A_N B_N

-----Output-----
If there is a pair of A and B that is consistent with the remaining records, print Yes; otherwise, print No.

-----Sample Input-----
3
1 -1
-1 4
-1 6

-----Sample Output-----
Yes

For example, if B_1 = 3, A_2 = 2, and A_3 = 5, all the requirements are met.
In this case, there is a moment when both Person 1 and Person 2 were on the elevator, which is fine since C_1 = C_2 = 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider an undirected graph containing $N$ nodes and $\mbox{M}$ edges. Each edge $\textit{M}_i$ has an integer cost, $C_i$, associated with it.

The penalty of a path is the bitwise OR of every edge cost in the path between a pair of nodes, $\mbox{A}$ and $\mbox{B}$. In other words, if a path contains edges $M_1,M_2,\ldots,M_k$, then the penalty for this path is $C_1$ OR $C_2$ OR ... OR $C_{k}$.

Given a graph and two nodes, $\mbox{A}$ and $\mbox{B}$, find the path between $\mbox{A}$ and $\mbox{B}$ having the minimal possible penalty and print its penalty; if no such path exists, print $-1$ to indicate that there is no path from $\mbox{A}$ to $\mbox{B}$.

Note: Loops and multiple edges are allowed. The bitwise OR operation is known as or in Pascal and as | in C++ and Java.

Input Format

The first line contains two space-separated integers, $N$ (the number of nodes) and $\mbox{M}$ (the number of edges), respectively.

Each line $\boldsymbol{i}$ of the $\mbox{M}$ subsequent lines contains three space-separated integers $U_i$, $V_i$, and $C_i$, respectively, describing edge $\textit{M}_i$ connecting the nodes $U_i$ and $V_i$ and its associated penalty ($C_i$).

The last line contains two space-separated integers, $\mbox{A}$ (the starting node) and $\mbox{B}$ (the ending node), respectively.

Constraints

$1\leq N\leq10^3$
$1\leq M\leq10^4$
$1\leq C_i<1024$
$1\leq U_i,V_i\leq N$
$1\leq A,B\leq N$
$A\neq B$

Output Format

Print the minimal penalty for the optimal path from node $\mbox{A}$ to node $\mbox{B}$; if no path exists from node $\mbox{A}$ to node $\mbox{B}$, print $-1$.

Sample Input
3 4
1 2 1
1 2 1000
2 3 3
1 3 100
1 3

Sample Output
3

Explanation

The optimal path is $1\rightarrow2\rightarrow3$. 

$C_{(1,2)}=1$ and $C_{(2,3)}=3$. 

The penalty for this path is: $1$ OR $3=3$, so we print $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An open-top box having a square bottom is placed on the floor. You see a number of needles vertically planted on its bottom.

You want to place a largest possible spheric balloon touching the box bottom, interfering with none of the side walls nor the needles.

Java Specific: Submitted Java programs may not use "java.awt.geom.Area". You may use it for your debugging purposes.

Figure H.1 shows an example of a box with needles and the corresponding largest spheric balloon. It corresponds to the first dataset of the sample input below.

<image>
Figure H.1. The upper shows an example layout and the lower shows the largest spheric balloon that can be placed.



Input

The input is a sequence of datasets. Each dataset is formatted as follows.


n w
x1 y1 h1
:
xn yn hn


The first line of a dataset contains two positive integers, n and w, separated by a space. n represents the number of needles, and w represents the height of the side walls.

The bottom of the box is a 100 × 100 square. The corners of the bottom face are placed at positions (0, 0, 0), (0, 100, 0), (100, 100, 0), and (100, 0, 0).

Each of the n lines following the first line contains three integers, xi, yi, and hi. (xi, yi, 0) and hi represent the base position and the height of the i-th needle. No two needles stand at the same position.

You can assume that 1 ≤ n ≤ 10, 10 ≤ w ≤ 200, 0 < xi < 100, 0 < yi < 100 and 1 ≤ hi ≤ 200. You can ignore the thicknesses of the needles and the walls.

The end of the input is indicated by a line of two zeros. The number of datasets does not exceed 1000.

Output

For each dataset, output a single line containing the maximum radius of a balloon that can touch the bottom of the box without interfering with the side walls or the needles. The output should not contain an error greater than 0.0001.

Example

Input

5 16
70 66 40
38 52 20
40 35 10
70 30 10
20 60 10
1 100
54 75 200
1 10
90 10 1
1 11
54 75 200
3 10
53 60 1
61 38 1
45 48 1
4 10
20 20 10
20 80 10
80 20 10
80 80 10
0 0


Output

26.00000
39.00000
130.00000
49.49777
85.00000
95.00000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Spike is competing in the Gauntlet of Fire for the title of Dragon Lord. To succeed, he needs to traverse the labyrinthine volcanic tunnels, avoiding the treacherous elements and making it from chamber to chamber as quickly as possible.

The cave has $N$ chambers and $M$ tunnels connecting these chambers; no tunnel connects a chamber to itself, and there is at most one tunnel between any two chambers. This cave has a special property: it is known that it is possible to travel between any two different chambers by taking one or more tunnels, and that there are at most two paths between any two different chambers that do not take any tunnel more than once.

For simplicity, we label the chambers $1, 2, \dots , N$; then, the $i^\text {th}$ tunnel connects chambers $A_ i$ and $B_ i$, and has a length of $L_ i$ meters.

Spike can travel at the fast, fast speed of $1$ meter per second. He wants to know the danger level of each chamber. The danger level of a chamber is simply the sum of the times, in seconds, required to travel from this chamber to every other chamber, assuming that one always takes the shortest path possible.

Help Spike determine the danger level of each chamber!

Since these numbers can be quite large, you should output only the remainders after dividing each number by $10^9+7$.

-----Input-----
The first line of input contains two integers, $N$ ($2 \leq N \leq 200000$) and $M$ ($N-1 \leq M \leq 400000$) the number of chambers and tunnels in the cave.

The next $M$ lines contain the descriptions of the tunnels. In particular, the $i^\text {th}$ of these lines contains three integers $A_ i$, $B_ i$ ($1\leq A_ i, B_ i \leq N$; $A_ i \neq B_ i$) and $L_ i$ ($1 \leq L_ i \leq 10^9$), denoting that the $i^\text {th}$ tunnel connects chambers $A_ i$ and $B_ i$, and has a length of $L_ i$ meters.

It is guaranteed that there is at most one tunnel between any two chambers, that it is possible to travel between any two different chambers by taking one or more tunnels, and that there are at most two paths between any two chambers that do not take any tunnel more than once.

-----Output-----
Output $N$ integers on a single line, separated by spaces. The $i^\text {th}$ of these integers should contain the danger level of chamber $i$.

Since these numbers can be quite large, you should output only the remainders after dividing each number by $10^9+7$.

-----Examples-----
Sample Input:
5 5
1 2 3
1 4 8
2 3 12
3 5 4
4 5 2
Sample Output:
35 39 36 27 29

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a list of integers, return the nth smallest integer in the list. **Only distinct elements should be considered** when calculating the answer. `n` will always be positive (`n > 0`)

If the nth small integer doesn't exist, return `-1` (C++) / `None` (Python) / `nil` (Ruby) / `null` (JavaScript).

Notes:
* "indexing" starts from 1
* huge lists (of 1 million elements) will be tested

## Examples

```python
nth_smallest([1, 3, 4, 5], 7)        ==> None  # n is more than the size of the list
nth_smallest([4, 3, 4, 5], 4)        ==> None  # 4th smallest integer doesn't exist
nth_smallest([45, -10, 4, 5, 4], 4)  ==> 45    # 4th smallest integer is 45
```

If you get a timeout, just try to resubmit your solution. However, if you ***always*** get a timeout, review your code.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two players are playing a game. First each of them writes an integer from 1 to 6, and then a dice is thrown. The player whose written number got closer to the number on the dice wins. If both payers have the same difference, it's a draw.

The first player wrote number a, the second player wrote number b. How many ways to throw a dice are there, at which the first player wins, or there is a draw, or the second player wins?


-----Input-----

The single line contains two integers a and b (1 ≤ a, b ≤ 6) — the numbers written on the paper by the first and second player, correspondingly.


-----Output-----

Print three integers: the number of ways to throw the dice at which the first player wins, the game ends with a draw or the second player wins, correspondingly.


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

Output
3 0 3

Input
2 4

Output
2 1 3



-----Note-----

The dice is a standard cube-shaped six-sided object with each side containing a number from 1 to 6, and where all numbers on all sides are distinct.

You can assume that number a is closer to number x than number b, if |a - x| < |b - x|.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Bad Luck Island is inhabited by three kinds of species: r rocks, s scissors and p papers. At some moments of time two random individuals meet (all pairs of individuals can meet equiprobably), and if they belong to different species, then one individual kills the other one: a rock kills scissors, scissors kill paper, and paper kills a rock. Your task is to determine for each species what is the probability that this species will be the only one to inhabit this island after a long enough period of time.

Input

The single line contains three integers r, s and p (1 ≤ r, s, p ≤ 100) — the original number of individuals in the species of rock, scissors and paper, respectively.

Output

Print three space-separated real numbers: the probabilities, at which the rocks, the scissors and the paper will be the only surviving species, respectively. The answer will be considered correct if the relative or absolute error of each number doesn't exceed 10 - 9.

Examples

Input

2 2 2


Output

0.333333333333 0.333333333333 0.333333333333


Input

2 1 2


Output

0.150000000000 0.300000000000 0.550000000000


Input

1 1 3


Output

0.057142857143 0.657142857143 0.285714285714

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