vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Recently, Chef found a new formula for computing powers of a sequence:
- You are given two sequences $A_1, A_2, \ldots, A_N$ and $(l_1, r_1), (l_2, r_2), \ldots, (l_N, r_N)$.
- The $1$-st power of the sequence $A$ is $A^1 = A$.
- For each $k > 1$, the $k$-th power of the sequence $A$ (denoted by $A^k$) is a sequence with length $N$ such that for each valid $i$, the $i$-th element of this sequence is (Ak)i=(Ak−1)li⊕(Ak−1)li+1⊕…⊕(Ak−1)ri−1⊕(Ak−1)ri.(Ak)i=(Ak−1)li⊕(Ak−1)li+1⊕…⊕(Ak−1)ri−1⊕(Ak−1)ri.(A^k)_i = (A^{k-1})_{l_i} \oplus (A^{k-1})_{l_i+1} \oplus \ldots \oplus (A^{k-1})_{r_i-1} \oplus (A^{k-1})_{r_i} \,.
After discovering this new formula, Chef tried to find $A^K$, but he felt that it is very time consuming. Therefore, Chef wants you to do it. Can you find the $K$-th power of $A$ for Chef?

-----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 two space-separated integers $N$ and $K$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $l_i$ and $r_i$.

-----Output-----
For each test case, print a single line containing $N$ space-separated integers $(A^K)_1, (A^K)_2, \ldots, (A^K)_N$.

-----Constraints-----
- $1 \le T \le 3$
- $1 \le N \le 500$
- $1 \le K \le 5 \cdot 10^7$
- $1 \le A_i \le 10^{18}$ for each valid $i$
- $1 \le l_i \le r_i \le N$ for each valid $i$

-----Subtasks-----
Subtask #1 (50 points):
- $T = 1$
- $N \le 100$
Subtask #2 (50 points): original constraints

-----Sample Input-----
1
3 2
1 2 3
1 2
2 3
1 3

-----Example Ouput-----
3 1 0

-----Explanation-----
Example case 1:
- $(A^2)_1 = A_1 \oplus A_2 = 1 \oplus 2 = 3$
- $(A^2)_2 = A_2 \oplus A_3 = 2 \oplus 3 = 1$
- $(A^2)_3 = A_1 \oplus A_2 \oplus A_3 =1 \oplus 2 \oplus 3 = 0$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has 3 boxes of sizes A, B, and C respectively. He puts the boxes in bags of size D (A ≤ B ≤ C ≤ D). Find the minimum number of bags Chef needs so that he can put each box in a bag. A bag can contain more than one box if the sum of sizes of boxes in the bag does not exceed the size of the bag.

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

- The first line contains T denoting the number of test cases. Then the test cases follow.
- Each test case contains four integers A, B, C, and D on a single line denoting the sizes of the boxes and bags.

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

For each test case, output on a single line the minimum number of bags Chef needs.

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

$1≤ T ≤ 100$
$1 ≤ A ≤ B ≤ C ≤ D ≤ 100$

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------ 
3
2 3 5 10
1 2 3 5
3 3 4 4

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

----- explanation 1 ------ 
Test case $1$:  The sum of sizes of boxes is $2 + 3 + 5 = 10$ which is equal to the size of a bag. Hence Chef can put all three boxes in a single bag.

Test case $2$: Chef can put boxes of size $1$ and $3$ in one bag and box of size $2$ in another bag.

Test case $3$: Chef puts all the boxes in separate bags as there is no way to put more than one box in a single bag.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Teacher Herkabe has decided to rank his students again. This time, he wants his list to also be aesthetically pleasant, so he has decided that similar names (those beginning with the same letter or sequence of letters) must be close to one another on the list. Therefore, he has devised the following rule:

For every two names on the list that begin with the same letter sequence, all names between them on the list must also begin with that letter sequence.

For example, consider the names MARTHA and MARY (characters from a beautiful story). They both begin with the sequence MAR, so names beginning with the same sequence (like MARCO and MARVIN) can appear in between (but not MAY, for example).

Notice that the lexicographically sorted ordering always satisfies this rule, but it is by no means the only valid ordering. Your task is determining how many different orderings satisfy the rule, i.e. how many options teacher Herkabe has for his ranking list.

-----Input-----
The first line of input contains the positive integer $N$ ($3 \leq N \leq 3\ 000$), the number of names. Each of the following $N$ lines contains a single name: a sequence of between $1$ and $3\ 000$ (inclusive) uppercase English letters. The names are distinct and given in no particular order.

-----Output-----
The first and only line of output must contain the required number of possible ranking lists, modulo $1\ 000\ 000\ 007$.

-----Examples-----
Sample Input 1:
3
IVO
JASNA
JOSIPA
Sample Output 1:
4

Sample Input 2:
5
MARICA
MARTA
MATO
MARA
MARTINA
Sample Output 2:
24

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Pasha decided to invite his friends to a tea party. For that occasion, he has a large teapot with the capacity of *w* milliliters and 2*n* tea cups, each cup is for one of Pasha's friends. The *i*-th cup can hold at most *a**i* milliliters of water.

It turned out that among Pasha's friends there are exactly *n* boys and exactly *n* girls and all of them are going to come to the tea party. To please everyone, Pasha decided to pour the water for the tea as follows:
 -  Pasha can boil the teapot exactly once by pouring there at most *w* milliliters of water; -  Pasha pours the same amount of water to each girl; -  Pasha pours the same amount of water to each boy; -  if each girl gets *x* milliliters of water, then each boy gets 2*x* milliliters of water. 
In the other words, each boy should get two times more water than each girl does.

Pasha is very kind and polite, so he wants to maximize the total amount of the water that he pours to his friends. Your task is to help him and determine the optimum distribution of cups between Pasha's friends.

Input Specification:
The first line of the input contains two integers, *n* and *w* (1<=≤<=*n*<=≤<=105, 1<=≤<=*w*<=≤<=109) — the number of Pasha's friends that are boys (equal to the number of Pasha's friends that are girls) and the capacity of Pasha's teapot in milliliters.

The second line of the input contains the sequence of integers *a**i* (1<=≤<=*a**i*<=≤<=109, 1<=≤<=*i*<=≤<=2*n*) — the capacities of Pasha's tea cups in milliliters.

Output Specification:
Print a single real number — the maximum total amount of water in milliliters that Pasha can pour to his friends without violating the given conditions. Your answer will be considered correct if its absolute or relative error doesn't exceed 10<=-<=6.

Demo Input:
['2 4\n1 1 1 1\n', '3 18\n4 4 4 2 2 2\n', '1 5\n2 3\n']

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

Note:
Pasha also has candies that he is going to give to girls but that is another task...

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.
For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.


Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.



Note:

The given numbers of 0s and 1s will both not exceed 100
The size of given string array won't exceed 600.



Example 1:

Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4

Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”



Example 2:

Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2

Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Permutation $p$ is a sequence of integers $p=[p_1, p_2, \dots, p_n]$, consisting of $n$ distinct (unique) positive integers between $1$ and $n$, inclusive. For example, the following sequences are permutations: $[3, 4, 1, 2]$, $[1]$, $[1, 2]$. The following sequences are not permutations: $[0]$, $[1, 2, 1]$, $[2, 3]$, $[0, 1, 2]$.

The important key is in the locked box that you need to open. To open the box you need to enter secret code. Secret code is a permutation $p$ of length $n$. 

You don't know this permutation, you only know the array $q$ of prefix maximums of this permutation. Formally:  $q_1=p_1$,  $q_2=\max(p_1, p_2)$,  $q_3=\max(p_1, p_2,p_3)$,  ...  $q_n=\max(p_1, p_2,\dots,p_n)$. 

You want to construct any possible suitable permutation (i.e. any such permutation, that calculated $q$ for this permutation is equal to the given array).


-----Input-----

The first line contains integer number $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow.

The first line of a test case contains one integer $n$ $(1 \le n \le 10^{5})$ — the number of elements in the secret code permutation $p$.

The second line of a test case contains $n$ integers $q_1, q_2, \dots, q_n$ $(1 \le q_i \le n)$ — elements of the array $q$ for secret permutation. It is guaranteed that $q_i \le q_{i+1}$ for all $i$ ($1 \le i < n$).

The sum of all values $n$ over all the test cases in the input doesn't exceed $10^5$.


-----Output-----

For each test case, print:  If it's impossible to find such a permutation $p$, print "-1" (without quotes).  Otherwise, print $n$ distinct integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). If there are multiple possible answers, you can print any of them. 


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

Output
1 3 4 5 2 
-1
2 1 
1 



-----Note-----

In the first test case of the example answer $[1,3,4,5,2]$ is the only possible answer:  $q_{1} = p_{1} = 1$;  $q_{2} = \max(p_{1}, p_{2}) = 3$;  $q_{3} = \max(p_{1}, p_{2}, p_{3}) = 4$;  $q_{4} = \max(p_{1}, p_{2}, p_{3}, p_{4}) = 5$;  $q_{5} = \max(p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) = 5$. 

It can be proved that there are no answers for the second test case of the example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a binary tree. The task is to find the Node with maximum GCD of the siblings of this tree. You have to return the value of the node whose two immediate children has the maximum gcd.
If there are multiple such nodes, return the node which has the maximum value.
Siblings: Nodes with the same parent are called siblings.
GCD (Greatest Common Divisor) of two positive integers is the largest positive integer that divides both numbers without a remainder.
Note:
Consider those nodes which have a sibling.
Return 0 if no such pair of siblings found.
 
Example 1:
Input:
              4
            /   \
           5     2
                /  \
               3    1
              /  \
             6   12
Output: 3
Explanation: For the above tree, the maximum
GCD for the siblings is formed for nodes 6 and 12
for the children of node 3.
 
Example 2:
Input: 
            1
          /   \
        3      5
      /  \    /  \
     6    9  4    8
Output: 5
Explanation: For the above tree, the maximum
GCD for the siblings is formed for nodes 4 and 8
for the children of node 5.
 
Your Task:
You don't need to take input. Just complete the function maxGCD() that takes the root node as a parameter and returns the value of the node whose two immediate children has the maximum gcd.
 
Expected Time Complexity: O(|Number of nodes|) .
Expected Auxiliary Space: O(height of the tree) .
 
Constraints:
1 <= Number of nodes <= 10^{5}
1 <= Data of a node <= 10^{5}

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

Time Limit: 2 seconds

Memory Limit: 64 megabytes

Problem Description:
As you know, Bob's brother lives in Flatland. In Flatland there are *n* cities, connected by *n*<=-<=1 two-way roads. The cities are numbered from 1 to *n*. You can get from one city to another moving along the roads.

The «Two Paths» company, where Bob's brother works, has won a tender to repair two paths in Flatland. A path is a sequence of different cities, connected sequentially by roads. The company is allowed to choose by itself the paths to repair. The only condition they have to meet is that the two paths shouldn't cross (i.e. shouldn't have common cities).

It is known that the profit, the «Two Paths» company will get, equals the product of the lengths of the two paths. Let's consider the length of each road equals 1, and the length of a path equals the amount of roads in it. Find the maximum possible profit for the company.

Input Specification:
The first line contains an integer *n* (2<=≤<=*n*<=≤<=200), where *n* is the amount of cities in the country. The following *n*<=-<=1 lines contain the information about the roads. Each line contains a pair of numbers of the cities, connected by the road *a**i*,<=*b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*).

Output Specification:
Output the maximum possible profit.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given N points (x_i,y_i) located on a two-dimensional plane.
Consider a subset S of the N points that forms a convex polygon.
Here, we say a set of points S forms a convex polygon when there exists a convex polygon with a positive area that has the same set of vertices as S. All the interior angles of the polygon must be strictly less than 180°.
For example, in the figure above, {A,C,E} and {B,D,E} form convex polygons; {A,C,D,E}, {A,B,C,E}, {A,B,C}, {D,E} and {} do not.
For a given set S, let n be the number of the points among the N points that are inside the convex hull of S (including the boundary and vertices). Then, we will define the score of S as 2^{n-|S|}.
Compute the scores of all possible sets S that form convex polygons, and find the sum of all those scores.
However, since the sum can be extremely large, print the sum modulo 998244353.

-----Constraints-----
 - 1≤N≤200
 - 0≤x_i,y_i<10^4 (1≤i≤N)
 - If i≠j, x_i≠x_j or y_i≠y_j.
 - x_i and y_i are integers.

-----Input-----
The input is given from Standard Input in the following format:
N
x_1 y_1
x_2 y_2
:
x_N y_N

-----Output-----
Print the sum of all the scores modulo 998244353.

-----Sample Input-----
4
0 0
0 1
1 0
1 1

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

We have five possible sets as S, four sets that form triangles and one set that forms a square. Each of them has a score of 2^0=1, so the answer is 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A National Geographic film crew is visiting the ZOO this week. They are creating a documentary about animal speed and they would like to film one or more cheetahs running at full pace. A solitary running cheetah has been filmed successfully many times. Therefore, the crew is also after a much more spectacular feat: As many as possible cheetahs sprinting on parallel tracks filmed together in one shot.

“No, that is impossible,” said the director. “We cannot squeeze those animals into some sort of a start box, as you probably imagine, and then open the box and make them run all at once. It is clearly too dangerous and unpredictable. No.”

“Then let us make more boxes and open some of them earlier and some of them later,” said one of the filmmakers. “Could that work?”

“And if we open the boxes with the slower cheetahs a bit earlier then after a while the faster ones will be overtaking the slower ones and that would be a great shot,” pointed out another filmmaker. “We would like to see the whole pack rather short with the last animals close the leading ones. As close as possible and at least for a moment.”

It was a long and difficult discussion which ensued, but in the end the circumstances of the experiment were agreed upon.

You are given the start time and the speed of each cheetah. The length of the pack, which is defined as the distance between the first and the last cheetah in the pack, might be different at different moments. Find the minimum length of the pack during the run, where all cheetahs must be running. You may also suppose that the track is so long that the minimum length of the pack happens at least a moment before the first cheetah reaches the finish line.

All start boxes will be so close that you may consider them to be in the same place. The $k$-th cheetah will be released from its start box at the given time $t_ k$. The $k$-th cheetah is expected to run the whole distance at constant speed $v_ k$.

-----Input-----
The first line contains the number of cheetahs $N$ ($1 \leq N \leq 100000$). Next, there are $N$ lines, each line contains two integers $t_ k$, $v_ k$ separated by spaces and representing the start time and velocity of the $k$-th cheetah ($1 \leq k \leq N$). All input values $t_ k$ and $v_ k$ are positive and less than $10^5$.

-----Output-----
Print a single line with one floating point number $L$ specifying the minimum length of the running pack. Your answer should not differ from the correct answer by more than $10^{-2}$. The length of the pack is the distance between the first and the last animal in the pack. The length can be measured at any time $T \geq \max _{k = 1, \ldots , N} t_ k$. We suppose that each cheetah is running at a constant speed for all the time from the start and also at its moment of release from the start box.

-----Examples-----
Sample Input 1:
2
1 1
1 1
Sample Output 1:
0.000

Sample Input 2:
2
1 99999
99999 99999
Sample Output 2:
9999700002.000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp is working on a new project called "Polychat". Following modern tendencies in IT, he decided, that this project should contain chat as well. To achieve this goal, Polycarp has spent several hours in front of his laptop and implemented a chat server that can process three types of commands:

  * Include a person to the chat ('Add' command). 
  * Remove a person from the chat ('Remove' command). 
  * Send a message from a person to all people, who are currently in the chat, including the one, who sends the message ('Send' command). 



Now Polycarp wants to find out the amount of outgoing traffic that the server will produce while processing a particular set of commands.

Polycarp knows that chat server sends no traffic for 'Add' and 'Remove' commands. When 'Send' command is processed, server sends l bytes to each participant of the chat, where l is the length of the message.

As Polycarp has no time, he is asking for your help in solving this problem.

Input

Input file will contain not more than 100 commands, each in its own line. No line will exceed 100 characters. Formats of the commands will be the following:

  * +<name> for 'Add' command. 
  * -<name> for 'Remove' command. 
  * <sender_name>:<message_text> for 'Send' command. 



<name> and <sender_name> is a non-empty sequence of Latin letters and digits. <message_text> can contain letters, digits and spaces, but can't start or end with a space. <message_text> can be an empty line.

It is guaranteed, that input data are correct, i.e. there will be no 'Add' command if person with such a name is already in the chat, there will be no 'Remove' command if there is no person with such a name in the chat etc.

All names are case-sensitive.

Output

Print a single number — answer to the problem.

Examples

Input

+Mike
Mike:hello
+Kate
+Dmitry
-Dmitry
Kate:hi
-Kate


Output

9


Input

+Mike
-Mike
+Mike
Mike:Hi   I am here
-Mike
+Kate
-Kate


Output

14

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As captain of your space ship you have never encountered a more fierce enemy than the one you have snuck upon now. You immediately bring out the big phaser cannon hoping to take out the flagship before they discover you. There is no room for mistakes and the shot will have to be perfect if you are to stand any chance at all against the flagship of the enemy. 

You start charging the phaser beam and retrieve the room layout of the flagship from the archives. You are situated directly above the enemy, from where the layout of the flagship can be modeled by a two-dimensional map of the rooms of the flagship. In this map, each room is a rectangle with sides parallel to the $x$ and $y$ axes (rectilinear), and no two rooms intersect (not even in a single point).

The phaser beam is configured by giving a point $(x, y)$ and an angle $\vartheta $. The phaser beam will start at $(x, y)$ and travel a distance $\ell $ in the direction specified by $\vartheta $, causing severe damage to every room touched by the phaser beam. Due to this, you aim at hitting as many rooms as possible.

The phaser beam is almost fully charged and the only missing piece is an optimal configuration of the weapon. Unfortunately, it turns out to be harder than you expected. However, there are still ten seconds before the charging is completed and hence you decide to make a computer program to solve the problem.

-----Input-----
The first line of input consists of two integers $r$ and $\ell $ ($1 \le r \le 15$, $1 \le \ell \le 1000$) where $r$ is the number of rooms in the flagship and $\ell $ is the length of a shot of the phaser.

Then follow $r$ lines, each of which contains four integers $x_1$, $y_1$, $x_2$, $y_2$ ($0 \le x_1 < x_2 \le 1000$, $0 \le y_1 < y_2 \le 1000$), indicating that there is a room in the flagship with lower left corner $(x_1, y_1)$ and upper right corner $(x_2, y_2)$.

-----Output-----
Output one line with the maximum number of rooms that can be hit by one phaser beam. Recall that if the beam touches a room it is counted as a hit.

You may assume that the answer is numerically stable in the following sense: if all rooms are expanded by a distance of $10^{-6}$ in all four directions, the answer does not change.

-----Examples-----
Sample Input:
5 8
2 1 4 5
5 1 12 4
5 5 9 10
1 6 4 10
2 11 7 14
Sample Output:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In mathematics, the Pythagorean theorem — is a relation in Euclidean geometry among the three sides of a right-angled triangle. In terms of areas, it states:

 In any right-angled triangle, the area of the square whose side is the hypotenuse (the side opposite the right angle) is equal to the sum of the areas of the squares whose sides are the two legs (the two sides that meet at a right angle). 

The theorem can be written as an equation relating the lengths of the sides a, b and c, often called the Pythagorean equation:

a^2 + b^2 = c^2

where c represents the length of the hypotenuse, and a and b represent the lengths of the other two sides.

 [Image] 

Given n, your task is to count how many right-angled triangles with side-lengths a, b and c that satisfied an inequality 1 ≤ a ≤ b ≤ c ≤ n.


-----Input-----

The only line contains one integer n (1 ≤ n ≤ 10^4) as we mentioned above.


-----Output-----

Print a single integer — the answer to the problem.


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

Output
1

Input
74

Output
35

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