vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
As Will is stuck in the Upside Down, he can still communicate with his mom, Joyce, through the Christmas lights (he can turn them on and off with his mind). He can't directly tell his mom where he is, because the monster that took him to the Upside Down will know and relocate him.  [Image] 

Thus, he came up with a puzzle to tell his mom his coordinates. His coordinates are the answer to the following problem.

A string consisting only of parentheses ('(' and ')') is called a bracket sequence. Some bracket sequence are called correct bracket sequences. More formally:  Empty string is a correct bracket sequence.  if s is a correct bracket sequence, then (s) is also a correct bracket sequence.  if s and t are correct bracket sequences, then st (concatenation of s and t) is also a correct bracket sequence. 

A string consisting of parentheses and question marks ('?') is called pretty if and only if there's a way to replace each question mark with either '(' or ')' such that the resulting string is a non-empty correct bracket sequence.

Will gave his mom a string s consisting of parentheses and question marks (using Morse code through the lights) and his coordinates are the number of pairs of integers (l, r) such that 1 ≤ l ≤ r ≤ |s| and the string s_{l}s_{l} + 1... s_{r} is pretty, where s_{i} is i-th character of s.

Joyce doesn't know anything about bracket sequences, so she asked for your help.


-----Input-----

The first and only line of input contains string s, consisting only of characters '(', ')' and '?' (2 ≤ |s| ≤ 5000).


-----Output-----

Print the answer to Will's puzzle in the first and only line of output.


-----Examples-----
Input
((?))

Output
4

Input
??()??

Output
7



-----Note-----

For the first sample testcase, the pretty substrings of s are:  "(?" which can be transformed to "()".  "?)" which can be transformed to "()".  "((?)" which can be transformed to "(())".  "(?))" which can be transformed to "(())".  

For the second sample testcase, the pretty substrings of s are:  "??" which can be transformed to "()".  "()".  "??()" which can be transformed to "()()".  "?()?" which can be transformed to "(())".  "??" which can be transformed to "()".  "()??" which can be transformed to "()()".  "??()??" which can be transformed to "()()()".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recall that a binary search tree is a rooted binary tree, whose nodes each store a key and each have at most two distinguished subtrees, left and right. The key in each node must be greater than any key stored in the left subtree, and less than any key stored in the right subtree.

The depth of a vertex is the number of edges on the simple path from the vertex to the root. In particular, the depth of the root is 0.

Let's call a binary search tree perfectly balanced if there doesn't exist a binary search tree with the same number of vertices that has a strictly smaller sum of depths of its vertices.

Let's call a binary search tree with integer keys striped if both of the following conditions are satisfied for every vertex v: 

  * If v has a left subtree whose root is u, then the parity of the key of v is different from the parity of the key of u. 
  * If v has a right subtree whose root is w, then the parity of the key of v is the same as the parity of the key of w. 



You are given a single integer n. Find the number of perfectly balanced striped binary search trees with n vertices that have distinct integer keys between 1 and n, inclusive. Output this number modulo 998 244 353.

Input

The only line contains a single integer n (1 ≤ n ≤ 10^6), denoting the required number of vertices.

Output

Output the number of perfectly balanced striped binary search trees with n vertices and distinct integer keys between 1 and n, inclusive, modulo 998 244 353.

Examples

Input


4


Output


1


Input


3


Output


0

Note

In the first example, this is the only tree that satisfies the conditions: <image>

In the second example, here are various trees that don't satisfy some condition: <image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
My birthday is coming up. Alas, I am getting old and would like to feel young again. Fortunately, I have come up with an excellent way of feeling younger: if I write my age as a number in an appropriately chosen base $b$, then it appears to be smaller. For instance, suppose my age in base $10$ is $32$. Written in base $16$ it is only $20$!

However, I cannot choose an arbitrary base when doing this. If my age written in base $b$ contains digits other than $0$ to $9$, then it will be obvious that I am cheating, which defeats the purpose. In addition, if my age written in base $b$ is too small then it would again be obvious that I am cheating.

Given my age $y$ and a lower bound $\ell $ on how small I want my age to appear, find the largest base $b$ such that $y$ written in base $b$ contains only decimal digits, and is at least $\ell $ when interpreted as a number in base $10$.

-----Input-----
The input consists of a single line containing two base 10 integers $y$ ($10 \le y \le 10^{18}$ – yes, I am very old) and $\ell $ ($10 \le \ell \le y$).

-----Output-----
Display the largest base $b$ as described above.

-----Examples-----
Sample Input:
32 20
Sample Output:
16

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 The sequence of `Chando` is an infinite sequence of all Chando's numbers in ascending order.

 A number is called `Chando's` if it is an integer that can be represented as a sum of different positive integer powers of 5.

 The first Chando's numbers is 5 (5^1). And the following nth Chando's numbers are:
 ```
 25  (5^2)
 30  (5^1 + 5^2)
 125 (5^3)
 130 (5^1 + 5^3)
 150 (5^2 + 5^3)
 ...
 ...
 ```

 Your task is to find the Chando's nth number for a given `n`.

# Input/Output


 - `[input]` integer `n`

  `1 <= n <= 7000`


 - `[output]` an integer

  nth Chando's number

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Momiji has got a rooted tree, consisting of n nodes. The tree nodes are numbered by integers from 1 to n. The root has number 1. Momiji decided to play a game on this tree.

The game consists of several steps. On each step, Momiji chooses one of the remaining tree nodes (let's denote it by v) and removes all the subtree nodes with the root in node v from the tree. Node v gets deleted as well. The game finishes when the tree has no nodes left. In other words, the game finishes after the step that chooses the node number 1.

Each time Momiji chooses a new node uniformly among all the remaining nodes. Your task is to find the expectation of the number of steps in the described game.

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of nodes in the tree. The next n - 1 lines contain the tree edges. The i-th line contains integers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — the numbers of the nodes that are connected by the i-th edge.

It is guaranteed that the given graph is a tree.

Output

Print a single real number — the expectation of the number of steps in the described game.

The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

Examples

Input

2
1 2


Output

1.50000000000000000000


Input

3
1 2
1 3


Output

2.00000000000000000000

Note

In the first sample, there are two cases. One is directly remove the root and another is remove the root after one step. Thus the expected steps are: 

1 × (1 / 2) + 2 × (1 / 2) = 1.5

In the second sample, things get more complex. There are two cases that reduce to the first sample, and one case cleaned at once. Thus the expected steps are: 

1 × (1 / 3) + (1 + 1.5) × (2 / 3) = (1 / 3) + (5 / 3) = 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Saket loves to play with strings. One day , while he was having fun with Cyclic Permutations of available strings to him, he observed that despite being scarce in numbers Vowels were really clingy.Being clingy means for almost every given string, there was a Cyclic Permutation in which atleast two vowels were together.
So he decided to check this property for all the available strings to him. As the number of strings can be very large, help Saket determine whether the given string is clingy or not.

-----Input:-----
The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
First line of every test case contains an integer N$N$ denoting the length of the string.
Second line contains a string S$S$ of length N$N$, consisting only of uppercase english alphabets.

-----Output:-----
For each test case, print a single line containing "Yes" if any of the cyclic permutations of the string is clingy else print "No".

-----Constraints-----
- 1≤T≤1000$1 \leq T \leq 1000$
- 1≤N≤1000$1 \leq N \leq 1000$
- String S$S$ consists of only upper case english alphabets.

-----Subtasks-----
- 20 points : 1≤N≤5$1 \leq N \leq 5$
- 80 points : Original$Original$ Constraints$Constraints$

-----Sample Input:-----
2
5
AUXFC
6
XBCDEF

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

No

-----EXPLANATION:-----
Example$Example$ case1:$ case 1: $ One of the cyclic permutation is the original string itself, which has "A" and "U" together.
Example$Example$ case2:$ case 2: $     None of the cyclic permutation will have 2 vowels together.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Imagine a funnel filled with letters. The bottom letter drops out of the funnel and onto a conveyor belt:

```
  \b,c/  -->   \b,c/
   \a/   -->    \ /
                 a
-------     -------
```
If there are two letters above a gap, the smaller letter falls into the gap.
```
  \b,c/   -->   \  c/ 
   \ /    -->    \b/   
a            a         
-------      -------
```
Of course, this can create a new gap, which must also be filled in the same way:
```
  \f,e,d/  -->  \f, ,d/
   \  c/   -->   \e,c/ 
    \b/           \b/   
   a            a         
  -------      -------
```
Once all the gaps above it have been filled, the bottom letter drops out of the funnel and onto the conveyorbelt. The process continues until all letters have fallen onto the conveyor. (New letters fall onto the end of the existing string)

**KATA GOAL: Return the string on the conveyorbelt after all letters have fallen**.
```
\f, ,d/      \f, ,d/   --> etc -->    \     /
 \e,c/        \e,c/    --> etc -->     \   /
  \b/    -->   \ /     --> etc -->      \ /
a           a   b                   abcdef
-------     -------                 -------
```
All letters in the funnel will be unique i.e. in every comparison one letter will be strictly smaller than the other. The funnel will be presented as a nested list, e.g:
```
[["d","a","c"],
   ["b","e"],
     ["f"]]
```
The value of a letter is defined by its codepoint. Note: this means all capital letters are defined as smaller than all lower-case letters, but your language's comparison operator will probably treat it that way automatically.

The funnels will always be "nice" -- every layer will have 1 item more than the layer below, and every layer will be full, and generally there's no funny business or surprises to consider. The only characters used are standard uppercase and lowercase letters A-Z and a-z. The tests go up to 9 layer funnel.

### Fully Worked Example
```
\d,a,c/      \d,a,c/      \d,a,c/ -->  \d   c/     
 \b,e/        \b,e/  -->   \  e/  -->   \a,e/
  \f/   -->    \ /   -->    \b/          \b/  --> 
                f        f            f
------      -------      -------      -------


\d   c/      \d   c/ -->  \    c/      \    c/     
 \a,e/  -->   \  e/  -->   \d,e/        \d,e/  -->
  \ /   -->    \a/          \a/   -->    \ /   -->
f  b        fb           fb           fb  a
------      -------      -------      -------


 \    c/      \    c/      \    c/ -->  \     /     
  \  e/        \  e/  -->   \   /  -->   \  c/   
   \d/   -->    \ /   -->    \e/          \e/  -->
fba          fba d       fbad          fbad
-------      -------     --------      -------


  \     /      \     /      \     /
   \  c/  -->   \   /        \   / 
    \ /          \c/   -->    \ /   
fbad e       fbade        fbadec         
-------      -------      -------

DONE. Return "fbadec".

```

**For a bigger funneling challenge, check out [this kata](https://www.codewars.com/kata/create-a-funnel) by @myjinxin2015.**

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bizon the Champion isn't just charming, he also is very smart.

While some of us were learning the multiplication table, Bizon the Champion had fun in his own manner. Bizon the Champion painted an n × m multiplication table, where the element on the intersection of the i-th row and j-th column equals i·j (the rows and columns of the table are numbered starting from 1). Then he was asked: what number in the table is the k-th largest number? Bizon the Champion always answered correctly and immediately. Can you repeat his success?

Consider the given multiplication table. If you write out all n·m numbers from the table in the non-decreasing order, then the k-th number you write out is called the k-th largest number.


-----Input-----

The single line contains integers n, m and k (1 ≤ n, m ≤ 5·10^5; 1 ≤ k ≤ n·m).


-----Output-----

Print the k-th largest number in a n × m multiplication table.


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

Output
2

Input
2 3 4

Output
3

Input
1 10 5

Output
5



-----Note-----

A 2 × 3 multiplication table looks like this:

1 2 3

2 4 6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a multiset containing several integers. Initially, it contains $a_1$ elements equal to $1$, $a_2$ elements equal to $2$, ..., $a_n$ elements equal to $n$.

You may apply two types of operations:  choose two integers $l$ and $r$ ($l \le r$), then remove one occurrence of $l$, one occurrence of $l + 1$, ..., one occurrence of $r$ from the multiset. This operation can be applied only if each number from $l$ to $r$ occurs at least once in the multiset;  choose two integers $i$ and $x$ ($x \ge 1$), then remove $x$ occurrences of $i$ from the multiset. This operation can be applied only if the multiset contains at least $x$ occurrences of $i$. 

What is the minimum number of operations required to delete all elements from the multiset?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 5000$).

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


-----Output-----

Print one integer — the minimum number of operations required to delete all elements from the multiset.


-----Examples-----
Input
4
1 4 1 1

Output
2

Input
5
1 0 1 0 1

Output
3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarpus loves lucky numbers. Everybody knows that lucky numbers are positive integers, whose decimal representation (without leading zeroes) contain only the lucky digits *x* and *y*. For example, if *x*<==<=4, and *y*<==<=7, then numbers 47, 744, 4 are lucky.

Let's call a positive integer *a* undoubtedly lucky, if there are such digits *x* and *y* (0<=≤<=*x*,<=*y*<=≤<=9), that the decimal representation of number *a* (without leading zeroes) contains only digits *x* and *y*.

Polycarpus has integer *n*. He wants to know how many positive integers that do not exceed *n*, are undoubtedly lucky. Help him, count this number.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=109) — Polycarpus's number.

Output Specification:
Print a single integer that says, how many positive integers that do not exceed *n* are undoubtedly lucky.

Demo Input:
['10\n', '123\n']

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

Note:
In the first test sample all numbers that do not exceed 10 are undoubtedly lucky.

In the second sample numbers 102, 103, 104, 105, 106, 107, 108, 109, 120, 123 are not undoubtedly lucky.

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 (numbered $1$ through $N$) and a sequence of integers $A_1, A_2, \ldots, A_N$. You may choose an arbitrary permutation $p_1, p_2, \ldots, p_N$ of the integers $1$ through $N$. Then, for each vertex $i$, you should assign the value $A_{p_i}$ to this vertex.
The profit of a path between two vertices $u$ and $v$ is the sum of the values assigned to the vertices on that path (including $u$ and $v$).
Let's consider only (undirected) paths that start at a leaf and end at a different leaf. Calculate the maximum possible value of the sum of profits of all such paths. Since this value could be very large, compute it modulo $10^9 + 7$.

-----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$.
- Each of the following $N−1$ lines contains two space-separated integers $u$ and $v$ denoting that vertices $u$ and $v$ are connected by an edge.

-----Output-----
For each test case, print a single line containing one integer — the maximum sum of profits, modulo $10^9 + 7$.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N \le 300,000$
- $1 \le A_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $5 \cdot 10^5$

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

-----Example Output-----
24
15

-----Explanation-----
Example case 1: $(1, 4, 2, 3)$ is one of the possible permutations that give the optimal answer. Then, the profits of paths between pairs of vertices $(1, 3)$, $(1, 4)$ and $(3, 4)$ are $7$, $8$ and $9$ respectively.
Example case 2: Here, any permutation could be chosen.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a programming language in which every program is a non-empty sequence of "<" and ">" signs and digits. Let's explain how the interpreter of this programming language works. A program is interpreted using movement of instruction pointer (IP) which consists of two parts.

  * Current character pointer (CP); 
  * Direction pointer (DP) which can point left or right; 



Initially CP points to the leftmost character of the sequence and DP points to the right.

We repeat the following steps until the first moment that CP points to somewhere outside the sequence.

  * If CP is pointing to a digit the interpreter prints that digit then CP moves one step according to the direction of DP. After that the value of the printed digit in the sequence decreases by one. If the printed digit was 0 then it cannot be decreased therefore it's erased from the sequence and the length of the sequence decreases by one. 
  * If CP is pointing to "<" or ">" then the direction of DP changes to "left" or "right" correspondingly. Then CP moves one step according to DP. If the new character that CP is pointing to is "<" or ">" then the previous character will be erased from the sequence. 



If at any moment the CP goes outside of the sequence the execution is terminated.

It's obvious the every program in this language terminates after some steps.

We have a sequence s1, s2, ..., sn of "<", ">" and digits. You should answer q queries. Each query gives you l and r and asks how many of each digit will be printed if we run the sequence sl, sl + 1, ..., sr as an independent program in this language.

Input

The first line of input contains two integers n and q (1 ≤ n, q ≤ 105) — represents the length of the sequence s and the number of queries. 

The second line contains s, a sequence of "<", ">" and digits (0..9) written from left to right. Note, that the characters of s are not separated with spaces. 

The next q lines each contains two integers li and ri (1 ≤ li ≤ ri ≤ n) — the i-th query.

Output

For each query print 10 space separated integers: x0, x1, ..., x9 where xi equals the number of times the interpreter prints i while running the corresponding program. Print answers to the queries in the order they are given in input.

Examples

Input

7 4
1&gt;3&gt;22&lt;
1 3
4 7
7 7
1 7


Output

0 1 0 1 0 0 0 0 0 0
2 2 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
2 3 2 1 0 0 0 0 0 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese  and Russian. 

------ Sereja and Arrays ------ 

Sereja have an array that consist of n integers a1, a2, ..., an (0 ≤ ai ≤ 1). Sereja can make next operation:  fix some integer i (1 ≤ i ≤ n - k + 1)  

subtract 1 from values: ai, ai + 1, ..., ai + k - 1Sereja call array a good if it is possible to make some operations, that he can and get array that contain only zeros. Now Sereja interested in next question: how many good arrays a with length n exist?

------ Input ------ 
First line contain integer T — number of testcases. T tests follow. Each testcase is given by two integers n and k.

------ Constraints ------ 
$ 1 ≤ T ≤ 10 $ $ 1 ≤ k ≤ n ≤ 105 $ 

------ Output ------ 
For each testcase output answer modulo 109 + 7.

------ Note ------ 

Test #0-1(25 points) n  ≤ 15
Test #2(25 points) n  ≤ 100
Test #3(50 points) n  ≤ 100000

----- Sample Input 1 ------ 
3
3 3
5 2
5 1
----- Sample Output 1 ------ 
2
8
32

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Fair Nut is going to travel to the Tree Country, in which there are $n$ cities. Most of the land of this country is covered by forest. Furthermore, the local road system forms a tree (connected graph without cycles). Nut wants to rent a car in the city $u$ and go by a simple path to city $v$. He hasn't determined the path, so it's time to do it. Note that chosen path can consist of only one vertex.

A filling station is located in every city. Because of strange law, Nut can buy only $w_i$ liters of gasoline in the $i$-th city. We can assume, that he has infinite money. Each road has a length, and as soon as Nut drives through this road, the amount of gasoline decreases by length. Of course, Nut can't choose a path, which consists of roads, where he runs out of gasoline. He can buy gasoline in every visited city, even in the first and the last.

He also wants to find the maximum amount of gasoline that he can have at the end of the path. Help him: count it.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 3 \cdot 10^5$) — the number of cities.

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($0 \leq w_{i} \leq 10^9$) — the maximum amounts of liters of gasoline that Nut can buy in cities.

Each of the next $n - 1$ lines describes road and contains three integers $u$, $v$, $c$ ($1 \leq u, v \leq n$, $1 \leq c \leq 10^9$, $u \ne v$), where $u$ and $v$ — cities that are connected by this road and $c$ — its length.

It is guaranteed that graph of road connectivity is a tree.


-----Output-----

Print one number — the maximum amount of gasoline that he can have at the end of the path.


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

Output
3

Input
5
6 3 2 5 0
1 2 10
2 3 3
2 4 1
1 5 1

Output
7



-----Note-----

The optimal way in the first example is $2 \to 1 \to 3$.  [Image] 

The optimal way in the second example is $2 \to 4$.  [Image]

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