vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Ultra-Fast Mathematician

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Shapur was an extremely gifted student. He was great at everything including Combinatorics, Algebra, Number Theory, Geometry, Calculus, etc. He was not only smart but extraordinarily fast! He could manage to sum 1018 numbers in a single second.

One day in 230 AD Shapur was trying to find out if any one can possibly do calculations faster than him. As a result he made a very great contest and asked every one to come and take part.

In his contest he gave the contestants many different pairs of numbers. Each number is made from digits 0 or 1. The contestants should write a new number corresponding to the given pair of numbers. The rule is simple: The *i*-th digit of the answer is 1 if and only if the *i*-th digit of the two given numbers differ. In the other case the *i*-th digit of the answer is 0.

Shapur made many numbers and first tried his own speed. He saw that he can perform these operations on numbers of length ∞ (length of a number is number of digits in it) in a glance! He always gives correct answers so he expects the contestants to give correct answers, too. He is a good fellow so he won't give anyone very big numbers and he always gives one person numbers of same length.

Now you are going to take part in Shapur's contest. See if you are faster and more accurate.

Input Specification:
There are two lines in each input. Each of them contains a single number. It is guaranteed that the numbers are made from 0 and 1 only and that their length is same. The numbers may start with 0. The length of each number doesn't exceed 100.

Output Specification:
Write one line — the corresponding answer. Do not omit the leading 0s.

Demo Input:
['1010100\n0100101\n', '000\n111\n', '1110\n1010\n', '01110\n01100\n']

Demo Output:
['1110001\n', '111\n', '0100\n', '00010\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Guddu was participating in a programming contest. He only had one problem left when his mother called him for dinner. Guddu is well aware how angry his mother could get if he was late for dinner and he did not want to sleep on an empty stomach, so he had to leave that last problem to you. Can you solve it on his behalf?
For a given sequence of positive integers $A_1, A_2, \ldots, A_N$, you are supposed to find the number of triples $(i, j, k)$ such that $1 \le i < j \le k \le N$ and
Ai⊕Ai+1⊕…⊕Aj−1=Aj⊕Aj+1⊕…⊕Ak,Ai⊕Ai+1⊕…⊕Aj−1=Aj⊕Aj+1⊕…⊕Ak,A_i \oplus A_{i+1} \oplus \ldots \oplus A_{j-1} = A_j \oplus A_{j+1} \oplus \ldots \oplus A_k \,,
where $\oplus$ denotes bitwise XOR.

-----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 a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of triples.

-----Constraints-----
- $1 \le T \le 10$
- $2 \le N \le 10^5$
- $1 \le A_i \le 10^6$ for each valid $i$

-----Subtasks-----
Subtask #1 (20 points):
- $1 \le T \le 5$
- $1 \le N \le 100$
Subtask #2 (30 points):
- $1 \le T \le 5$
- $1 \le N \le 1,000$
Subtask #3 (50 points): original constraints

-----Example Input-----
1
3
5 2 7

-----Example Output-----
2

-----Explanation-----
Example case 1: The triples are $(1, 3, 3)$, since $5 \oplus 2 = 7$, and $(1, 2, 3)$, since $5 = 2 \oplus 7$.

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

There is a war and nobody knows - the alphabet war!  
There are two groups of hostile letters. The tension between left side letters and right side letters was too high and the war began.

# Task

Write a function that accepts `fight` string consists of only small letters and return who wins the fight. When the left side wins return `Left side wins!`, when the right side wins return `Right side wins!`, in other case return `Let's fight again!`.

The left side letters and their power:
```
 w - 4
 p - 3
 b - 2
 s - 1
```
The right side letters and their power:
```
 m - 4
 q - 3
 d - 2
 z - 1
```
The other letters don't have power and are only victims.

# Example

# Alphabet war Collection



Alphavet war 


Alphabet war - airstrike - letters massacre


Alphabet wars - reinforces massacre


Alphabet wars - nuclear strike


Alphabet war - Wo lo loooooo priests join the war

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tree with N vertices 1,2,\ldots,N, and positive integers c_1,c_2,\ldots,c_N. The i-th edge in the tree (1 \leq i \leq N-1) connects Vertex a_i and Vertex b_i.

We will write a positive integer on each vertex in T and calculate our score as follows:

* On each edge, write the smaller of the integers written on the two endpoints.
* Let our score be the sum of the integers written on all the edges.



Find the maximum possible score when we write each of c_1,c_2,\ldots,c_N on one vertex in T, and show one way to achieve it. If an integer occurs multiple times in c_1,c_2,\ldots,c_N, we must use it that number of times.

Constraints

* 1 \leq N \leq 10000
* 1 \leq a_i,b_i \leq N
* 1 \leq c_i \leq 10^5
* The given graph is a tree.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 \ldots c_N


Output

Use the following format:


M
d_1 \ldots d_N


where M is the maximum possible score, and d_i is the integer to write on Vertex i. d_1,d_2,\ldots,d_N must be a permutation of c_1,c_2,\ldots,c_N. If there are multiple ways to achieve the maximum score, any of them will be accepted.

Examples

Input

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


Output

10
1 2 3 4 5


Input

5
1 2
1 3
1 4
1 5
3141 59 26 53 59


Output

197
59 26 3141 59 53

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Roy has taken a liking to the Binary Search Trees(BST). He is interested in knowing the number of ways an array $\mbox{A}$ of $N$ integers can be arranged to form a BST. Thus, he tries a few combinations, and notes down the numbers at the odd levels and the numbers at the even levels. 

You're given two values, alpha and beta. Can you calculate the sum of Liking of all possible BST's that can be formed from an array of $N$ integers? Liking of each BST is defined as follows 

(sum of numbers on even levels * alpha) - (sum of numbers on odd levels * beta)

Note 

The root element is at level $0$ ( Even )
The elements smaller or equal to the parent element are present in the left subtree, elements greater than or equal to the parent element are present in the right subtree.  Explained here

If the answer is no less than $10^{9}+9$, output the answer % $10^{9}+9$. 

(If the answer is less than $0$, keep adding $10^{9}+9$ until the value turns non negative.)

Input Format 

The first line of input file contains an integer, $\mathbf{T}$, denoting the number of test cases to follow. 

Each testcase comprises of $3$ lines. 

The first line contains $N$, the number of integers. 

The second line contains two space separated integers, alpha and beta. 

The third line contains space separated $N$ integers_, denoting the $i^{\mbox{th}}$ integer in array $A[i]$.  

Output Format 

Output $\mathbf{T}$ lines. Each line contains the answer to its respective test case. 

Constraints  

$1\leq T\leq10$ 

$1\leq N\leq150$ 

$1\leq A[i]\leq10^9$ 

$1\leq alpha,beta\leq10^9$  

Sample Input

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

Sample Output

1
0
6
54

Explanation

There are $\begin{array}{c}4\end{array}$ test cases in total. 

For the first test case, only $1$ BST can be formed with 1 as the root node. Hence the Liking / sum is $1$. 

For the second test case, we get 2 BSTs of the form, the Liking of the first tree is $1*1-2*1=-1$ and $2*1-1*1=1$, this sums to $0$, hence the answer. 

1                  2 
 \                /
  2              1

For the third test case, we get $5$ BSTs. The Liking of each of the BST from left  to right are $2,-2,4,2,0$ which sums to $\boldsymbol{6}$ and hence the answer.  

1            2                 3          3      1
 \          / \               /          /        \
  2        1   3             1          2          3
   \                          \        /          /
    3                          2      1          2

Similarly, for the fourth test case, the answer is $54$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Some large corporation where Polycarpus works has its own short message service center (SMSC). The center's task is to send all sorts of crucial information. Polycarpus decided to check the efficiency of the SMSC. 

For that, he asked to give him the statistics of the performance of the SMSC for some period of time. In the end, Polycarpus got a list of n tasks that went to the SMSC of the corporation. Each task was described by the time it was received by the SMSC and the number of text messages to send. More formally, the i-th task was described by two integers t_{i} and c_{i} — the receiving time (the second) and the number of the text messages, correspondingly.

Polycarpus knows that the SMSC cannot send more than one text message per second. The SMSC uses a queue to organize its work. Consider a time moment x, the SMSC work at that moment as follows:

  If at the time moment x the queue is not empty, then SMSC sends one message from the queue (SMSC gets the message from the head of the queue). Otherwise it doesn't send messages at the time moment x.  If at the time moment x SMSC receives a task, then it adds to the queue all the messages from this task (SMSC adds messages to the tail of the queue). Note, that the messages from the task cannot be send at time moment x. That's because the decision about sending message or not is made at point 1 before adding these messages to the queue. 

Given the information about all n tasks, Polycarpus wants to count two values: the time when the last text message was sent and the maximum size of the queue at some time. Help him count these two characteristics he needs to evaluate the efficiency of the SMSC.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^3) — the number of tasks of the SMSC. Next n lines contain the tasks' descriptions: the i-th line contains two space-separated integers t_{i} and c_{i} (1 ≤ t_{i}, c_{i} ≤ 10^6) — the time (the second) when the i-th task was received and the number of messages to send, correspondingly.

It is guaranteed that all tasks were received at different moments of time. It is guaranteed that the tasks are sorted in the chronological order, that is, t_{i} < t_{i} + 1 for all integer i (1 ≤ i < n).


-----Output-----

In a single line print two space-separated integers — the time when the last text message was sent and the maximum queue size at a certain moment of time.


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

Output
3 1

Input
1
1000000 10

Output
1000010 10

Input
3
3 3
4 3
5 3

Output
12 7



-----Note-----

In the first test sample: 

  second 1: the first message has appeared in the queue, the queue's size is 1;  second 2: the first message is sent, the second message has been received, the queue's size is 1;  second 3: the second message is sent, the queue's size is 0, 

Thus, the maximum size of the queue is 1, the last message was sent at the second 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a list of words, each word consists of English lowercase letters.
Let's say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2.  For example, "abc" is a predecessor of "abac".
A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.
Return the longest possible length of a word chain with words chosen from the given list of words.
 
Example 1:
Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".

 
Note:

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of English lowercase letters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a single integer N, your task is to find the sum of the square of the first N odd natural Numbers.
 
Example 1:
Input: 2
Output: 10
Explanation: 1^{2 + }3^{2}^{ }= 10
Example 2: 
Input: 3
Output: 35
Explanation: 1^{2} + 3^{2} + 5^{2} = 35
 
Your Task:
You don't need to read or print anything. Your task is to complete the function sum_of_square_oddNumbers() which takes N as the input parameter and returns the sum of the first N odd natural numbers.
 
Expected Time Complexity: O(1)
Expected Space Complexity: O(1)
 
Constraints:
1 <= N <= 10000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rohit has n empty boxes lying on the ground in a line. The size of the boxes is given in the form of an array $a$. The size of the ith box is denoted by $a[i]$. Since Rohit has a tiny room, there is a shortage of space. Therefore, he has to reduce the number of boxes on the ground by putting a box into another box that is at least twice the size of the current box i.e if we have to put the ith box into the jth box then $( 2*a[i] ) <= a[j]$.
Each box can contain a maximum of one box and the box which is kept in another box cannot
hold any box itself.
Find the minimum number of boxes that will remain on the ground after putting boxes into each other.

-----Input:-----
- The first line contains a single integer n.
- The next n lines contain the integer a[i] - the size of the i-th box.

-----Output:-----
Output a single integer denoting the minimum number of boxes remaining on the ground.

-----Constraints-----
- $1 \leq n \leq 5*10^5$
- $1 \leq a[i] \leq 10^5$

-----Subtasks-----
- 30 points : $1 \leq n \leq 10^2$
- 70 points : $1 \leq n \leq 5*10^5$

-----Sample Input:-----
5
16
1
4
8
2

-----Sample Output:-----
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Binod is a youtuber and he is busy in the fame of social media so he asked you to help him solve a problem.
You have been given an array of $positive$ $integers$ $a_{1},a_{2},a_{3},...,a_{i},...,a_{n}$ of size n.You have to find the smallest length of the subarray such that the length of the subarray must be $strictly$ greater than k and it's sum also must be $strictly$ greater than s. 

-----Input Format :------
- The first line of input contains three space-separated integers n, k and s
- The second line contains n space-separated integers,describing the array a 

-----Output Format:-----
- Print a single integer :- The smallest length of subarray if exists, Otherwise print "-1" (without quotes) 

-----Constraints:------
- $1 \leq n, k \leq 10^{6}$
- $1 \leq  a_{1},a_{2},a_{3},...,a_{i},...,a_{n}\leq 10^{9}$ 
- $1 \leq s \leq 10^{15}$ Subtask #1 (30 points):
- $1 \leq n, k \leq 10^{3}$ Subtask #2 (70 points):
$Original$ $Constraints$ 

-----Sample Test Cases:------

-----Example 1:-----
5 1 5

1 2 3 4 5 

-----Output :-----
2 

-----Explanation-----
$\textbf{There are two possibles answers} :$ 
- Index starts at 3 and ends at 4 have a sum of 7 which is strictly greater than 5 and has a length of subarray greater than 1.  
- Index starts at 4 and ends at 5 have a sum of 9 which is strictly greater than 5 and has a length of subarray greater than 1.
Any of the possible scenarios gives the same answer.

-----Example 2:-----
3 2 1

9 9 1 

-----Output :-----
3

-----Explanation :-----
- Each value in array index satisfies the condition sum greater than 1 but to satisfy the condition of length greater than 2 choose the subarray of length 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S which only contains lowercase alphabets. Find the length of the longest substring of S such that the characters in it can be rearranged to form a palindrome. 
Example 1:
Input:
S = "aabe"
Output:
3
Explanation:
The substring "aab" can be rearranged to
"aba" which is the longest palindrome
possible for this String.
Example 2:
Input:
S = "adbabd"
Output:
6
Explanation:
The whole string “adbabd” can be
rearranged to form a palindromic substring.
One possible arrangement is "abddba".
Thus, output length of the string is 6. 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function longestSubstring() which takes a String S as input and returns the length of largest possible Palindrome.
Expected Time Complexity: O(|S|*26)
Expected Auxiliary Space: O(|S|*26)
Constraints:
1 ≤ |S| ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Professor Abacus has just built a new computing engine for making numerical tables. It was designed to calculate the values of a polynomial function in one variable at several points at a time. With the polynomial function f(x) = x2 + 2x + 1, for instance, a possible expected calculation result is 1 (= f(0)), 4 (= f(1)), 9 (= f(2)), 16 (= f(3)), and 25 (= f(4)).

It is a pity, however, the engine seemingly has faulty components and exactly one value among those calculated simultaneously is always wrong. With the same polynomial function as above, it can, for instance, output 1, 4, 12, 16, and 25 instead of 1, 4, 9, 16, and 25.

You are requested to help the professor identify the faulty components. As the first step, you should write a program that scans calculation results of the engine and finds the wrong values.



Input

The input is a sequence of datasets, each representing a calculation result in the following format.

d
v0
v1
...
vd+2


Here, d in the first line is a positive integer that represents the degree of the polynomial, namely, the highest exponent of the variable. For instance, the degree of 4x5 + 3x + 0.5 is five and that of 2.4x + 3.8 is one. d is at most five.

The following d + 3 lines contain the calculation result of f(0), f(1), ... , and f(d + 2) in this order, where f is the polynomial function. Each of the lines contains a decimal fraction between -100.0 and 100.0, exclusive.

You can assume that the wrong value, which is exactly one of f(0), f(1), ... , and f(d+2), has an error greater than 1.0. Since rounding errors are inevitable, the other values may also have errors but they are small and never exceed 10-6.

The end of the input is indicated by a line containing a zero.

Output

For each dataset, output i in a line when vi is wrong.

Example

Input

2
1.0
4.0
12.0
16.0
25.0
1
-30.5893962764
5.76397083962
39.3853798058
74.3727663177
4
42.4715310246
79.5420238202
28.0282396675
-30.3627807522
-49.8363481393
-25.5101480106
7.58575761381
5
-21.9161699038
-48.469304271
-24.3188578417
-2.35085940324
-9.70239202086
-47.2709510623
-93.5066246072
-82.5073836498
0


Output

2
1
1
6

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Appleman has a tree with *n* vertices. Some of the vertices (at least one) are colored black and other vertices are colored white.

Consider a set consisting of *k* (0<=≤<=*k*<=&lt;<=*n*) edges of Appleman's tree. If Appleman deletes these edges from the tree, then it will split into (*k*<=+<=1) parts. Note, that each part will be a tree with colored vertices.

Now Appleman wonders, what is the number of sets splitting the tree in such a way that each resulting part will have exactly one black vertex? Find this number modulo 1000000007 (109<=+<=7).

Input Specification:
The first line contains an integer *n* (2<=<=≤<=*n*<=≤<=105) — the number of tree vertices. 

The second line contains the description of the tree: *n*<=-<=1 integers *p*0,<=*p*1,<=...,<=*p**n*<=-<=2 (0<=≤<=*p**i*<=≤<=*i*). Where *p**i* means that there is an edge connecting vertex (*i*<=+<=1) of the tree and vertex *p**i*. Consider tree vertices are numbered from 0 to *n*<=-<=1.

The third line contains the description of the colors of the vertices: *n* integers *x*0,<=*x*1,<=...,<=*x**n*<=-<=1 (*x**i* is either 0 or 1). If *x**i* is equal to 1, vertex *i* is colored black. Otherwise, vertex *i* is colored white.

Output Specification:
Output a single integer — the number of ways to split the tree modulo 1000000007 (109<=+<=7).

Demo Input:
['3\n0 0\n0 1 1\n', '6\n0 1 1 0 4\n1 1 0 0 1 0\n', '10\n0 1 2 1 4 4 4 0 8\n0 0 0 1 0 1 1 0 0 1\n']

Demo Output:
['2\n', '1\n', '27\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Duff is addicted to meat! Malek wants to keep her happy for *n* days. In order to be happy in *i*-th day, she needs to eat exactly *a**i* kilograms of meat.

There is a big shop uptown and Malek wants to buy meat for her from there. In *i*-th day, they sell meat for *p**i* dollars per kilogram. Malek knows all numbers *a*1,<=...,<=*a**n* and *p*1,<=...,<=*p**n*. In each day, he can buy arbitrary amount of meat, also he can keep some meat he has for the future.

Malek is a little tired from cooking meat, so he asked for your help. Help him to minimize the total money he spends to keep Duff happy for *n* days.

Input Specification:
The first line of input contains integer *n* (1<=≤<=*n*<=≤<=105), the number of days.

In the next *n* lines, *i*-th line contains two integers *a**i* and *p**i* (1<=≤<=*a**i*,<=*p**i*<=≤<=100), the amount of meat Duff needs and the cost of meat in that day.

Output Specification:
Print the minimum money needed to keep Duff happy for *n* days, in one line.

Demo Input:
['3\n1 3\n2 2\n3 1\n', '3\n1 3\n2 1\n3 2\n']

Demo Output:
['10\n', '8\n']

Note:
In the first sample case: An optimal way would be to buy 1 kg on the first day, 2 kg on the second day and 3 kg on the third day.

In the second sample case: An optimal way would be to buy 1 kg on the first day and 5 kg (needed meat for the second and third day) on the second day.

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.