vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
One day, Takahashi was given the following problem from Aoki:

* You are given a tree with N vertices and an integer K. The vertices are numbered 1 through N. The edges are represented by pairs of integers (a_i, b_i).
* For a set S of vertices in the tree, let f(S) be the minimum number of the vertices in a subtree of the given tree that contains all vertices in S.
* There are <image> ways to choose K vertices from the trees. For each of them, let S be the set of the chosen vertices, and find the sum of f(S) over all <image> ways.
* Since the answer may be extremely large, print it modulo 924844033(prime).



Since it was too easy for him, he decided to solve this problem for all K = 1,2,...,N.

Constraints

* 2 ≦ N ≦ 200,000
* 1 ≦ a_i, b_i ≦ N
* The given graph is a tree.

Input

The input is given from Standard Input in the following format:


N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}


Output

Print N lines. The i-th line should contain the answer to the problem where K=i, modulo 924844033.

Examples

Input

3
1 2
2 3


Output

3
7
3


Input

4
1 2
1 3
1 4


Output

4
15
13
4


Input

7
1 2
2 3
2 4
4 5
4 6
6 7


Output

7
67
150
179
122
45
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
#Sorting on planet Twisted-3-7

There is a planet... in a galaxy far far away. It is exactly like our planet, but it has one difference:
#The values of the digits 3 and 7 are twisted.
Our 3 means 7 on the planet Twisted-3-7. And 7 means 3.

Your task is to create a method, that can sort an array the way it would be sorted on Twisted-3-7.

7 Examples from a friend from Twisted-3-7:
```
[1,2,3,4,5,6,7,8,9] -> [1,2,7,4,5,6,3,8,9]
[12,13,14] -> [12,14,13]
[9,2,4,7,3] -> [2,7,4,3,9]
```

There is no need for a precheck. The array will always be not null and will always contain at least one number.

You should not modify the input array!

Have fun coding it and please don't forget to vote and rank this kata! :-) 

I have also created other katas. Take a look if you enjoyed this kata!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a_1, a_2, \dots , a_n$ and two integers $m$ and $k$.

You can choose some subarray $a_l, a_{l+1}, \dots, a_{r-1}, a_r$. 

The cost of subarray $a_l, a_{l+1}, \dots, a_{r-1}, a_r$ is equal to $\sum\limits_{i=l}^{r} a_i - k \lceil \frac{r - l + 1}{m} \rceil$, where $\lceil x \rceil$ is the least integer greater than or equal to $x$. 

The cost of empty subarray is equal to zero.

For example, if $m = 3$, $k = 10$ and $a = [2, -4, 15, -3, 4, 8, 3]$, then the cost of some subarrays are:  $a_3 \dots a_3: 15 - k \lceil \frac{1}{3} \rceil = 15 - 10 = 5$;  $a_3 \dots a_4: (15 - 3) - k \lceil \frac{2}{3} \rceil = 12 - 10 = 2$;  $a_3 \dots a_5: (15 - 3 + 4) - k \lceil \frac{3}{3} \rceil = 16 - 10 = 6$;  $a_3 \dots a_6: (15 - 3 + 4 + 8) - k \lceil \frac{4}{3} \rceil = 24 - 20 = 4$;  $a_3 \dots a_7: (15 - 3 + 4 + 8 + 3) - k \lceil \frac{5}{3} \rceil = 27 - 20 = 7$. 

Your task is to find the maximum cost of some subarray (possibly empty) of array $a$.


-----Input-----

The first line contains three integers $n$, $m$, and $k$ ($1 \le n \le 3 \cdot 10^5, 1 \le m \le 10, 1 \le k \le 10^9$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$).


-----Output-----

Print the maximum cost of some subarray of array $a$.


-----Examples-----
Input
7 3 10
2 -4 15 -3 4 8 3

Output
7

Input
5 2 1000
-13 -4 -9 -20 -11

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A group of friends has just played a round of miniature golf. Miniature golf courses consist of a number of holes. Each player takes a turn to play each hole by hitting a ball repeatedly until it drops into the hole. A player’s score on that hole is the number of times they hit the ball. To prevent incompetent players slowing down the game too much, there is also an upper limit $\ell $ (a positive integer) on the score: if a player has hit the ball $\ell $ times without the ball dropping into the hole, the score for that hole is recorded as $\ell $ and that player’s turn is over. The total score of each player is simply the sum of their scores on all the holes. Naturally, a lower score is considered better.

There is only one problem: none of the players can remember the value of the integer $\ell $. They decide that they will not apply any upper limit while playing, allowing each player to keep playing until the ball drops into the hole. After the game they intend to look up the value of $\ell $ and adjust the scores, replacing any score on a hole that is larger than $\ell $ with $\ell $.

The game has just finished, but the players have not yet looked up $\ell $. They wonder what their best possible ranks are. For this problem, the rank of a player is the number of players who achieved an equal or lower total score after the scores are adjusted with $\ell $. For example, if the adjusted scores of the players are $3$, $5$, $5$, $4$, and $3$, then their ranks are $2$, $5$, $5$, $3$ and $2$ respectively.

Given the scores of the players on each hole, determine the smallest possible rank for each player.

-----Input-----
The first line of input contains two integers $p$ and $h$, where $p$ ($2 \le p \le 500$) is the number of players and $h$ ($1 \le h \le 50$) is the number of holes. The next $p$ lines each contain $h$ positive integers. The $j^{\text {th}}$ number on the $i^{\text {th}}$ of these lines is the score for player $i$ on hole $j$, and does not exceed $10^9$.

-----Output-----
Output a line with the minimum possible rank for each player, in the same order as players are listed in the input.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is playing a variant of Blackjack, where 3 numbers are drawn and each number lies between 1 and 10 (with both 1 and 10 inclusive). Chef wins the game when the sum of these 3 numbers is exactly 21.

Given the first two numbers A and B, that have been drawn by Chef, what should be 3-rd number that should be drawn by the Chef in order to win the game?

Note that it is possible that Chef cannot win the game, no matter what is the 3-rd number. In such cases, report -1 as the answer. 

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

- The first line will contain an integer T - number of test cases. Then the test cases follow.
- The first and only line of each test case contains two integers A and B - the first and second number drawn by the Chef.

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

For each testcase, output the 3-rd number that should be drawn by the Chef in order to win the game. Output -1 if it is not possible for the Chef to win the game. 

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

$1 ≤ T ≤ 100$
$1 ≤ A, B ≤ 10$

----- Sample Input 1 ------ 
3
1 10
1 5
4 9
----- Sample Output 1 ------ 
10
-1
8
----- explanation 1 ------ 
Test case $1$: The first two numbers are $1$ and $10$. If the third number will be $10$, the resulting sum will be $1 + 10 + 10 = 21$. So Chef will win the game if the third number is $10$.

Test case $2$: The first two numbers are $1$ and $5$. There is no number between $1$ and $10$, that can make the resulting sum $21$. Hence, the answer will be $-1$ in this test case.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Little Elephant and Broken Sorting

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The Little Elephant loves permutations of integers from 1 to *n* very much. But most of all he loves sorting them. To sort a permutation, the Little Elephant repeatedly swaps some elements. As a result, he must receive a permutation 1,<=2,<=3,<=...,<=*n*.

This time the Little Elephant has permutation *p*1,<=*p*2,<=...,<=*p**n*. Its sorting program needs to make exactly *m* moves, during the *i*-th move it swaps elements that are at that moment located at the *a**i*-th and the *b**i*-th positions. But the Little Elephant's sorting program happened to break down and now on every step it can equiprobably either do nothing or swap the required elements.

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

We'll call a pair of integers *i*,<=*j* (1<=≤<=*i*<=&lt;<=*j*<=≤<=*n*) an inversion in permutatuon *p*1,<=*p*2,<=...,<=*p**n*, if the following inequality holds: *p**i*<=&gt;<=*p**j*.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=1000,<=*n*<=&gt;<=1) — the permutation size and the number of moves. The second line contains *n* distinct integers, not exceeding *n* — the initial permutation. Next *m* lines each contain two integers: the *i*-th line contains integers *a**i* and *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*,<=*a**i*<=≠<=*b**i*) — the positions of elements that were changed during the *i*-th move.

Output Specification:
In the only line print a single real number — the answer to the problem. The answer will be considered correct if its relative or absolute error does not exceed 10<=-<=6.

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

Demo Output:
['0.500000000\n', '3.000000000\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is very organised in whatever he does and likes to maintain statistics of his work. Chef has expertise in web development and hence is a regular contributor on a forum. Chef sometimes makes multiple contributions in a single day.. Each day chef makes at least 1 contribution he is assigned a shade of green. The greater the number of contribution in a single day the darker shade of green he gets assigned and vice versa. Your job is to find out the number of days chef is assigned a same shade of green and print the number of times chef is assigned a unique shade of green.

-----INPUT-----
The first line of input contains an integer T denoting the number of test cases. T test cases follow.

The first line of each test case contains an integer N denoting the number of days chef has contributed towards the forum.

The next line contains N spaced integers the number of contributions chef has made if he has made any.

-----OUTPUT-----

The output will contain numbers on separate lines that show the number of individual green shades chef has earned in ascending order of intensity of the shades of green.

-----CONSTRAINTS-----
1 <= T <= 25

5 <= N <= 50

1 <= Ai <= 50

-----EXAMPLE-----Input:

1

7

20 6 5 3 3 1 1
Output:

1: 2

3: 2

5: 1

6: 1

20: 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has two integers X and Y. Chef wants to perform some operations to make both X and Y zero simultaneously. In one operation, Chef can either:
set X := 2 \cdot X
or set Y := 2 \cdot Y
or set X := X - 1 and Y := Y - 1

Chef is a little busy with preparing the contest. Help him find the minimum number of operations required to make both X and Y equal to 0 simultaneously. If it is impossible to do so after any number of operations, print -1.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two space separated integers X and Y.

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

For each test case, print the minimum number of operations required to make X and Y zero simultaneously. If it is impossible to do so after any number of operations, print -1 instead.

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

$1 ≤ T ≤ 3 \cdot 10^{5}$
$0 ≤ X , Y ≤ 10^{18}$

----- Sample Input 1 ------ 
2
1 2
99999999999999999 99999999999999999
----- Sample Output 1 ------ 
3
99999999999999999
----- explanation 1 ------ 
Let $(x, y)$ denote the values of $X$ and $Y$ respectively.

Test case 1: Three operations are required: $(1, 2) \xrightarrow{X := X \cdot 2}{} (2, 2) \xrightarrow[Y := Y - 1]{X := X - 1} (1, 1) \xrightarrow[Y := Y - 1]{X := X - 1} (0, 0)$

It can be proven that it is impossible in fewer operations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An elephant decided to visit his friend. It turned out that the elephant's house is located at point 0 and his friend's house is located at point x(x > 0) of the coordinate line. In one step the elephant can move 1, 2, 3, 4 or 5 positions forward. Determine, what is the minimum number of steps he need to make in order to get to his friend's house.


-----Input-----

The first line of the input contains an integer x (1 ≤ x ≤ 1 000 000) — The coordinate of the friend's house.


-----Output-----

Print the minimum number of steps that elephant needs to make to get from point 0 to point x.


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

Output
1

Input
12

Output
3



-----Note-----

In the first sample the elephant needs to make one step of length 5 to reach the point x.

In the second sample the elephant can get to point x if he moves by 3, 5 and 4. There are other ways to get the optimal answer but the elephant cannot reach x in less than three moves.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider an infinite full binary tree (each node has two children except the leaf nodes) defined as follows. For a node labelled v its left child will be labelled 2*v and its right child will be labelled 2*v+1. The root is labelled as 1.
You are given N queries of the form i j. For each query, you have to print the length of the shortest path between node labelled i and  node labelled j.

-----Input-----
First line contains N, the number of queries. Each query consists of two space separated integers i and j in one line.

-----Output-----
For each query, print the required answer in one line.

-----Constraints-----
- 1 ≤ N ≤ 105
- 1 ≤ i,j ≤ 109

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

Output:
1
2
3

-----Explanation-----
For first query, 1 is directly connected to 2 by an edge. Hence distance 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The length of the longest common prefix of two strings s=s_1 s_2 … s_n and t = t_1 t_2 … t_m is defined as the maximum k ≤ min(n, m) such that s_1 s_2 … s_k equals t_1 t_2 … t_k. Let's denote the longest common prefix of two strings s and t as lcp(s,t).

Z-function of a string s_1 s_2 ... s_n is a sequence of integers z_1, z_2, …, z_n, where z_i = lcp(s_1 s_2 … s_n,\ \ s_i s_{i+1} ... s_n). Ж-function of a string s is defined as z_1 + z_2 + … + z_n.

You're given a string s=s_1 s_2 … s_n and q queries. Each query is described by two integers l_i and r_i, where 1 ≤ l_i ≤ r_i ≤ n. The answer for the query is defined as Ж-function of the string s_{l_i} s_{l_i +1} … s_{r_i}.

Input

The first line contains the string s, consisting of lowercase English letters (1 ≤ |s| ≤ 200 000). The second line contains one integer q — the number of queries (1 ≤ q ≤ 200 000). Each of the following q lines contains two integers l_i and r_i, describing the query (1 ≤ l_i ≤ r_i ≤ |s|).

Output

For every query output one integer: the value of Ж-function of the corresponding substring.

Examples

Input


abbd
4
2 3
1 3
3 3
1 4


Output


3
3
1
4


Input


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


Output


3
6
6
1
3

Note

In the first sample case there are four queries:

  * the first query corresponds to the substring bb, and its Ж-function equals 2 + 1 = 3;
  * the second query corresponds to the substring abb, and its Ж-function equals 3 + 0 + 0 = 3;
  * the third query corresponds to the substring b, and its Ж-function equals 1.
  * the fourth query corresponds to the substring abdd, and its Ж-function equals 4 + 0 + 0 + 0= 4.

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

John found a path to a treasure, and while searching for its precise location he wrote a list of directions using symbols `"^"`, `"v"`, `"<"`, `">"` which mean `north`, `east`, `west`, and `east` accordingly. On his way John had to try many different paths, sometimes walking in circles, and even missing the treasure completely before finally noticing it.

___

## Task

Simplify the list of directions written by John by eliminating any loops.

**Note**: a loop is any sublist of directions which leads John to the coordinate he had already visited.

___

## Examples

```
simplify("<>>")        ==  ">"
simplify("<^^>v<^^^")  ==  "<^^^^"
simplify("")           ==  ""
simplify("^< > v
    ^   v
> > C > D > >
^   ^   v
^ < B < <
    ^
    A
```

John visits points `A -> B -> C -> D -> B -> C -> D`, realizes that `-> C -> D -> B` steps are meaningless and removes them, getting this path: `A -> B -> (*removed*) -> C -> D`.

```
    ∙ ∙ ∙
    ∙   ∙
> > C > D > >
^   ∙   ∙
^ < B ∙ ∙
    ^
    A
```

Following the final, simplified route John visits points `C` and `D`, but for the first time, not the second (because we ignore the steps made on a hypothetical path), and he doesn't need to alter the directions list anymore.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has a graph containing both directed (oriented) and undirected (non-oriented) edges. There can be multiple edges between a pair of vertices.

Vasya has picked a vertex s from the graph. Now Vasya wants to create two separate plans:

  1. to orient each undirected edge in one of two possible directions to maximize number of vertices reachable from vertex s; 
  2. to orient each undirected edge in one of two possible directions to minimize number of vertices reachable from vertex s. 



In each of two plans each undirected edge must become directed. For an edge chosen directions can differ in two plans.

Help Vasya find the plans.

Input

The first line contains three integers n, m and s (2 ≤ n ≤ 3·105, 1 ≤ m ≤ 3·105, 1 ≤ s ≤ n) — number of vertices and edges in the graph, and the vertex Vasya has picked.

The following m lines contain information about the graph edges. Each line contains three integers ti, ui and vi (1 ≤ ti ≤ 2, 1 ≤ ui, vi ≤ n, ui ≠ vi) — edge type and vertices connected by the edge. If ti = 1 then the edge is directed and goes from the vertex ui to the vertex vi. If ti = 2 then the edge is undirected and it connects the vertices ui and vi.

It is guaranteed that there is at least one undirected edge in the graph.

Output

The first two lines should describe the plan which maximizes the number of reachable vertices. The lines three and four should describe the plan which minimizes the number of reachable vertices.

A description of each plan should start with a line containing the number of reachable vertices. The second line of a plan should consist of f symbols '+' and '-', where f is the number of undirected edges in the initial graph. Print '+' as the j-th symbol of the string if the j-th undirected edge (u, v) from the input should be oriented from u to v. Print '-' to signify the opposite direction (from v to u). Consider undirected edges to be numbered in the same order they are given in the input.

If there are multiple solutions, print any of them.

Examples

Input

2 2 1
1 1 2
2 2 1


Output

2
-
2
+


Input

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


Output

6
++-
2
+-+

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

After Karen have found the deterministic winning (losing?) strategy for rock-paper-scissors, her brother, Koyomi, comes up with a new game as a substitute. The game works as follows.

A positive integer n is decided first. Both Koyomi and Karen independently choose n distinct positive integers, denoted by x_1, x_2, ..., x_{n} and y_1, y_2, ..., y_{n} respectively. They reveal their sequences, and repeat until all of 2n integers become distinct, which is the only final state to be kept and considered.

Then they count the number of ordered pairs (i, j) (1 ≤ i, j ≤ n) such that the value x_{i} xor y_{j} equals to one of the 2n integers. Here xor means the bitwise exclusive or operation on two integers, and is denoted by operators ^ and/or xor in most programming languages.

Karen claims a win if the number of such pairs is even, and Koyomi does otherwise. And you're here to help determine the winner of their latest game.


-----Input-----

The first line of input contains a positive integer n (1 ≤ n ≤ 2 000) — the length of both sequences.

The second line contains n space-separated integers x_1, x_2, ..., x_{n} (1 ≤ x_{i} ≤ 2·10^6) — the integers finally chosen by Koyomi.

The third line contains n space-separated integers y_1, y_2, ..., y_{n} (1 ≤ y_{i} ≤ 2·10^6) — the integers finally chosen by Karen.

Input guarantees that the given 2n integers are pairwise distinct, that is, no pair (i, j) (1 ≤ i, j ≤ n) exists such that one of the following holds: x_{i} = y_{j}; i ≠ j and x_{i} = x_{j}; i ≠ j and y_{i} = y_{j}.


-----Output-----

Output one line — the name of the winner, that is, "Koyomi" or "Karen" (without quotes). Please be aware of the capitalization.


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

Output
Karen

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

Output
Karen



-----Note-----

In the first example, there are 6 pairs satisfying the constraint: (1, 1), (1, 2), (2, 1), (2, 3), (3, 2) and (3, 3). Thus, Karen wins since 6 is an even number.

In the second example, there are 16 such pairs, and Karen wins again.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integer sequences S and T of length N and M, respectively, both consisting of integers between 1 and 10^5 (inclusive).
In how many pairs of a subsequence of S and a subsequence of T do the two subsequences are the same in content?
Here the subsequence of A is a sequence obtained by removing zero or more elements from A and concatenating the remaining elements without changing the order.
For both S and T, we distinguish two subsequences if the sets of the indices of the removed elements are different, even if the subsequences are the same in content.
Since the answer can be tremendous, print the number modulo 10^9+7.

-----Constraints-----
 - 1 \leq N, M \leq 2 \times 10^3
 - The length of S is N.
 - The length of T is M.     
 - 1 \leq S_i, T_i \leq 10^5
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M
S_1 S_2 ... S_{N-1} S_{N}
T_1 T_2 ... T_{M-1} T_{M}

-----Output-----
Print the number of pairs of a subsequence of S and a subsequence of T such that the subsequences are the same in content, modulo 10^9+7.

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

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

S has four subsequences: (), (1), (3), (1, 3).
T has four subsequences: (), (3), (1), (3, 1).
There are 1 \times 1 pair of subsequences in which the subsequences are both (), 1 \times 1 pair of subsequences in which the subsequences are both (1), and 1 \times 1 pair of subsequences in which the subsequences are both (3), for a total of three pairs.

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