vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Let's write all the positive integer numbers one after another from 1 without any delimiters (i.e. as a single string). It will be the infinite sequence starting with 123456789101112131415161718192021222324252627282930313233343536...

Your task is to print the k-th digit of this sequence.

Input

The first and only line contains integer k (1 ≤ k ≤ 10000) — the position to process (1-based index).

Output

Print the k-th digit of the resulting infinite sequence.

Examples

Input


7


Output


7


Input


21


Output


5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have weather records at AtCoder Town for some consecutive three days. A string of length 3, S, represents the records - if the i-th character is S, it means it was sunny on the i-th day; if that character is R, it means it was rainy on that day.
Find the maximum number of consecutive rainy days in this period.

-----Constraints-----
 - |S| = 3
 - Each character of S is S or R.

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
Print the maximum number of consecutive rainy days in the period.

-----Sample Input-----
RRS

-----Sample Output-----
2

We had rain on the 1-st and 2-nd days in the period. Here, the maximum number of consecutive rainy days is 2, so we should print 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The main land of Japan called Honshu is an island surrounded by the sea. In such an island, it is natural to ask a question: "Where is the most distant point from the sea?" The answer to this question for Honshu was found in 1996. The most distant point is located in former Usuda Town, Nagano Prefecture, whose distance from the sea is 114.86 km.

In this problem, you are asked to write a program which, given a map of an island, finds the most distant point from the sea in the island, and reports its distance from the sea. In order to simplify the problem, we only consider maps representable by convex polygons.



Input

The input consists of multiple datasets. Each dataset represents a map of an island, which is a convex polygon. The format of a dataset is as follows.


n
x1    y1
.
.
.
xn    yn


Every input item in a dataset is a non-negative integer. Two input items in a line are separated by a space.

n in the first line is the number of vertices of the polygon, satisfying 3 ≤ n ≤ 100. Subsequent n lines are the x- and y-coordinates of the n vertices. Line segments (xi, yi) - (xi+1, yi+1) (1 ≤ i ≤ n - 1) and the line segment (xn, yn) - (x1, y1) form the border of the polygon in counterclockwise order. That is, these line segments see the inside of the polygon in the left of their directions. All coordinate values are between 0 and 10000, inclusive.

You can assume that the polygon is simple, that is, its border never crosses or touches itself. As stated above, the given polygon is always a convex one.

The last dataset is followed by a line containing a single zero.

Output

For each dataset in the input, one line containing the distance of the most distant point from the sea should be output. An output line should not contain extra characters such as spaces.

The answer should not have an error greater than 0.00001 (10-5 ). You may output any number of digits after the decimal point, provided that the above accuracy condition is satisfied.

Example

Input

4
0 0
10000 0
10000 10000
0 10000
3
0 0
10000 0
7000 1000
6
0 40
100 20
250 40
250 70
100 90
0 70
3
0 0
10000 10000
5000 5001
0


Output

5000.000000
494.233641
34.542948
0.353553

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a flower bed, there are N flowers, numbered 1,2,......,N. Initially, the heights of all flowers are 0.
You are given a sequence h=\{h_1,h_2,h_3,......\} as input. You would like to change the height of Flower k to h_k for all k (1 \leq  k \leq N), by repeating the following "watering" operation:
 - Specify integers l and r. Increase the height of Flower x by 1 for all x such that l \leq x \leq r.
Find the minimum number of watering operations required to satisfy the condition.

-----Constraints-----
 - 1 \leq N  \leq 100
 - 0 \leq h_i \leq 100
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
h_1 h_2 h_3 ...... h_N

-----Output-----
Print the minimum number of watering operations required to satisfy the condition.

-----Sample Input-----
4
1 2 2 1

-----Sample Output-----
2

The minimum number of watering operations required is 2.
One way to achieve it is:
 - Perform the operation with (l,r)=(1,3).
 - Perform the operation with (l,r)=(2,4).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a list of white pawns on a chessboard (any number of them, meaning from 0 to 64 and with the possibility to be positioned everywhere), determine how many of them have their backs covered by another. 
Pawns attacking upwards since we have only white ones.

Please remember that a pawn attack(and defend as well) only the 2 square on the sides in front of him. https://en.wikipedia.org/wiki/Pawn_(chess)#/media/File:Pawn_(chess)_movements.gif

This is how the chess board coordinates are defined:
ABCDEFGH8♜♞♝♛♚♝♞♜7♟♟♟♟♟♟♟♟65432♙♙♙♙♙♙♙♙1♖♘♗♕♔♗♘♖

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We are given a sequence of coplanar points and see all the possible triangles that may be generated which all combinations of three points.

We have the following list of points with the cartesian coordinates of each one:
```
Points [x, y]
   A   [1, 2]
   B   [3, 3]
   C   [4, 1]
   D   [1, 1]
   E   [4, -1]
```
With these points we may have the following triangles: ```ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE.``` There are three special ones: ```ABC, ACD and CDE```, that have an angle of 90°. All is shown in the picture below:



We need to count all the rectangle triangles that may be formed by a given list of points.

The case decribed above will be:
```python
count_rect_triang([[1, 2],[3, 3],[4, 1],[1, 1],[4, -1]]) == 3
```

Observe this case:
```python
count_rect_triang([[1, 2],[4, -1],[3, 3],[4, -1],[4, 1],[1, 1],[4, -1], [4, -1], [3, 3], [1, 2]]) == 3
```
If no rectangle triangles may be generated the function will output ```0```.

Enjoy it!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sherlock rolls a N faced die M times. He adds all the numbers he gets on all throws. What is the probability that he has a sum of K.   

A N faced die has all numbers from 1 to N written on it and each has equal probability of arriving when dice is thrown.

Input 
First line T, the number of testcases. Each testcase consists of M, N and K in one line.       

Output 
For each testcase, print required probability in scientific notation as defined follows:   
Output should be of the form "x y" where x is a floating point integer less than 10 and greater than or equal to 1 and y is a integer. This notation is equivalent to x * 10^-y. x should be rounded and output till 3 decimal digits.   
However, if probability is 0, output "0.000 0".     

Examples:
If output is supposed to be 0.0034567, output should be "3.457 3".    
If output is supposed to be 0.3034567, output should be "3.034 1".     

Constraints 
1 ≤ T ≤ 10     
1 ≤ N, M ≤ 50       
1 ≤ K ≤ 10000       

SAMPLE INPUT
2
1 5 2
2 3 2

SAMPLE OUTPUT
2.000 1
1.111 1

Explanation

For first testcase, sum=1,2,3,4,5 are all equally probable. Hence probability is 0.2.
For second testcase:
(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3) are all possible ways.
Out of these 1 has sum 2. So 1/9 is the answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that returns the index of the first occurence of the word "Wally".  "Wally" must not be part of another word, but it can be directly followed by a punctuation mark.  If no such "Wally" exists, return -1.


Examples:

"Wally" => 0

"Where's Wally" => 8

"Where's Waldo" => -1

"DWally Wallyd .Wally" => -1

"Hi Wally." => 3

"It's Wally's." => 5

"Wally Wally" => 0

"'Wally Wally" => 7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"Winter Is Coming". This is what they say in "Game of Thrones". This is yet another day in King's Landing and Tyrion Lannister is doing his job of "Hand of king". While looking at his ledger he finds a unique pattern with numbers. Tyrion has N numbers and he finds and there is always a sub-array(continuous subset) of numbers whose sum is divisible by N. To test his hypothesis he comes up with T(Test Cases) sets of N integers and tries to find smallest sub-array whose sum is divisible by N. If multiple answers are possible print the sub-array which occurs left most in array of integers.

Input
First line of input is T, number of test cases. Each test case has two lines. First line is N. Next line contains N integers, the array Tyrion considers to test his hypothesis.

Output
For each input Output the smallest sub-array with sum divisible by N. The index of range of sub-array to be be printed should be 1-based.

Constraints:
1 ≤ Elements of array ≤ 10^9
1 ≤ T ≤ 10
1 ≤ N ≤ 100000

Explanation:
Test Case 1: sum from index 3 to 3 is 3 divisible by 3. 
Test Case 2: sum from index 1 to 2 is 3 divisible by 3. 

SAMPLE INPUT
2
3
1 1 3
3
1 2 1SAMPLE OUTPUT
3 3
1 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a special undirected graph. It consists of 2n vertices numbered from 1 to 2n. The following properties hold for the graph:

  * there are exactly 3n-2 edges in the graph: n edges connect vertices having odd numbers with vertices having even numbers, n - 1 edges connect vertices having odd numbers with each other, and n - 1 edges connect vertices having even numbers with each other; 
  * for each edge (u, v) between a pair of vertices with odd numbers, there exists an edge (u + 1, v + 1), and vice versa; 
  * for each odd number u ∈ [1, 2n - 1], there exists an edge (u, u + 1); 
  * the graph is connected; moreover, if we delete all vertices with even numbers from it, and all edges incident to them, the graph will become a tree (the same applies to deleting odd vertices).



So, the graph can be represented as two trees having the same structure, and n edges connecting each vertex of the first tree to the corresponding vertex of the second tree.

Edges of the graph are weighted. The length of some simple path in the graph is the sum of weights of traversed edges.

You are given q queries to this graph; in each query, you are asked to compute the length of the shortest path between some pair of vertices in this graph. Can you answer all of the queries?

Input

The first line of the input contains one integer n (2 ≤ n ≤ 3 ⋅ 10^5).

The second line contains n integers w_{1, 2}, w_{3,4}, ..., w_{2n - 1, 2n} (1 ≤ w_{i, i + 1} ≤ 10^{12}). These integers describe the weights of the edges connecting odd vertices with even ones.

Then n-1 lines follow. i-th line contains four integers x_i, y_i, w_{i, 1} and w_{i, 2} (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i, 1 ≤ w_{i, j} ≤ 10^{12}); it describes two edges: one connecting 2x_i - 1 with 2y_i - 1 and having weight w_{i, 1}; another connecting 2x_i with 2y_i and having weight w_{i, 2}.

The next line contains one integer q (1 ≤ q ≤ 6 ⋅ 10^5) — the number of queries.

Then q lines follow, i-th line contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ 2n, u_i ≠ v_i), describing a query "compute the length of the shortest path between vertices u_i and v_i".

Output

Print q integers, i-th integer should be equal to the answer to the i-th query.

Example

Input


5
3 6 15 4 8
1 2 5 4
2 3 5 7
1 4 1 5
1 5 2 1
3
1 2
5 6
1 10


Output


3
15
4

Note

The graph in the first test looks like that:

<image>

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

Construct an array of length N containing only positive integers in the range [1, 1000] such that there doesn’t exist a subarray that has all elements occurring in even frequency and the maximum element in the array is minimized. In case there are multiple solutions, you can output any.

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

- First line will contain T, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, one integer N. 

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

For each test case, output in a single line N space-separated integers representing the required array. If there are multiple solutions, you may output any.

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

$1 ≤ T ≤ 500$
$1 ≤ N ≤ 1000$

----- Sample Input 1 ------ 
3
1
2
7
----- Sample Output 1 ------ 
1
2 1
1 2 3 2 1 2 3
----- explanation 1 ------ 
Test case $1$: $[1]$ is the obvious answer.

Test case $2$: Since we need two elements and they can't be the same (otherwise the frequency of that element of the whole array is even), $[2, 1]$ is the optimal answer. $[1, 2]$ is another optimal one.

Test case $3$: It can be proven that no construction exists with the maximum element of $2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef likes strings a lot but he likes palindromic strings more. Today, Chef has two strings A and B, each consisting of lower case alphabets.

Chef is eager to know whether it is possible to choose some non empty strings s1 and s2 where s1 is a substring of A, s2 is a substring of B such that s1 + s2 is a palindromic string. Here '+' denotes the concatenation between the strings.
Note:
A string is a palindromic string if it can be read same both forward as well as backward. To know more about palindromes click here.

-----Input-----
- First line of input contains a single integer T denoting the number of test cases.
- For each test case:
	
- First line contains the string A
- Second line contains the string B.

-----Output-----
For each test case, Print "Yes" (without quotes) if it possible to choose such strings s1 & s2. Print "No" (without quotes) otherwise.


-----Constraints-----
- 1 ≤ T ≤ 10 
- 1 ≤ |A|, |B| ≤ 1000 

-----Subtasks-----
-  Subtask 1: 1 ≤ |A|, |B| ≤ 10 : ( 40 pts )
-  Subtask 2: 1 ≤ |A|, |B| ≤ 1000 : ( 60 pts )

-----Example-----Input
3
abc
abc
a
b
abba
baab

Output
Yes
No
Yes

-----Explanation-----
- Test 1: One possible way of choosing s1 & s2 is s1 = "ab", s2 = "a" such that s1 + s2 i.e "aba" is a palindrome.
- Test 2: There is no possible way to choose s1 & s2 such that s1 + s2 is a palindrome.
- Test 3: You can figure it out yourself.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given $n$ pairs of integers $(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)$. All of the integers in the pairs are distinct and are in the range from $1$ to $2 \cdot n$ inclusive.

Let's call a sequence of integers $x_1, x_2, \ldots, x_{2k}$ good if either   $x_1 < x_2 > x_3 < \ldots < x_{2k-2} > x_{2k-1} < x_{2k}$, or  $x_1 > x_2 < x_3 > \ldots > x_{2k-2} < x_{2k-1} > x_{2k}$. 

You need to choose a subset of distinct indices $i_1, i_2, \ldots, i_t$ and their order in a way that if you write down all numbers from the pairs in a single sequence (the sequence would be $a_{i_1}, b_{i_1}, a_{i_2}, b_{i_2}, \ldots, a_{i_t}, b_{i_t}$), this sequence is good.

What is the largest subset of indices you can choose? You also need to construct the corresponding index sequence $i_1, i_2, \ldots, i_t$.


-----Input-----

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

Each of the next $n$ lines contain two numbers — $a_i$ and $b_i$ ($1 \le a_i, b_i \le 2 \cdot n$) — the elements of the pairs.

It is guaranteed that all integers in the pairs are distinct, that is, every integer from $1$ to $2 \cdot n$ is mentioned exactly once.


-----Output-----

In the first line print a single integer $t$ — the number of pairs in the answer.

Then print $t$ distinct integers $i_1, i_2, \ldots, i_t$ — the indexes of pairs in the corresponding order.


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

Output
3
1 5 3

Input
3
5 4
3 2
6 1

Output
3
3 2 1



-----Note-----

The final sequence in the first example is $1 < 7 > 3 < 5 > 2 < 10$.

The final sequence in the second example is $6 > 1 < 3 > 2 < 5 > 4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We are given a personal information string S, which may represent either an email address or a phone number.
We would like to mask this personal information according to the following rules:

1. Email address:
We define a name to be a string of length ≥ 2 consisting of only lowercase letters a-z or uppercase letters A-Z.
An email address starts with a name, followed by the symbol '@', followed by a name, followed by the dot '.' and followed by a name. 
All email addresses are guaranteed to be valid and in the format of "name1@name2.name3".
To mask an email, all names must be converted to lowercase and all letters between the first and last letter of the first name must be replaced by 5 asterisks '*'.

2. Phone number:
A phone number is a string consisting of only the digits 0-9 or the characters from the set {'+', '-', '(', ')', ' '}. You may assume a phone number contains 10 to 13 digits.
The last 10 digits make up the local number, while the digits before those make up the country code. Note that the country code is optional. We want to expose only the last 4 digits and mask all other digits.
The local number should be formatted and masked as "***-***-1111", where 1 represents the exposed digits.
To mask a phone number with country code like "+111 111 111 1111", we write it in the form "+***-***-***-1111".  The '+' sign and the first '-' sign before the local number should only exist if there is a country code.  For example, a 12 digit phone number mask should start with "+**-".
Note that extraneous characters like "(", ")", " ", as well as extra dashes or plus signs not part of the above formatting scheme should be removed.
 
Return the correct "mask" of the information provided.
 
Example 1:
Input: "LeetCode@LeetCode.com"
Output: "l*****e@leetcode.com"
Explanation: All names are converted to lowercase, and the letters between the
             first and last letter of the first name is replaced by 5 asterisks.
             Therefore, "leetcode" -> "l*****e".

Example 2:
Input: "AB@qq.com"
Output: "a*****b@qq.com"
Explanation: There must be 5 asterisks between the first and last letter 
             of the first name "ab". Therefore, "ab" -> "a*****b".

Example 3:
Input: "1(234)567-890"
Output: "***-***-7890"
Explanation: 10 digits in the phone number, which means all digits make up the local number.

Example 4:
Input: "86-(10)12345678"
Output: "+**-***-***-5678"
Explanation: 12 digits, 2 digits for country code and 10 digits for local number. 

Notes:

S.length <= 40.
Emails have length at least 8.
Phone numbers have length at least 10.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Colossal! — exclaimed Hawk-nose. — A programmer! That's exactly what we are looking for.Arkadi and Boris Strugatsky. Monday starts on Saturday

Reading the book "Equations of Mathematical Magic" Roman Oira-Oira and Cristobal Junta found an interesting equation: $a - (a \oplus x) - x = 0$ for some given $a$, where $\oplus$ stands for a bitwise exclusive or (XOR) of two integers (this operation is denoted as ^ or xor in many modern programming languages). Oira-Oira quickly found some $x$, which is the solution of the equation, but Cristobal Junta decided that Oira-Oira's result is not interesting enough, so he asked his colleague how many non-negative solutions of this equation exist. This task turned out to be too difficult for Oira-Oira, so he asks you to help.


-----Input-----

Each test contains several possible values of $a$ and your task is to find the number of equation's solution for each of them. The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of these values.

The following $t$ lines contain the values of parameter $a$, each value is an integer from $0$ to $2^{30} - 1$ inclusive.


-----Output-----

For each value of $a$ print exactly one integer — the number of non-negative solutions of the equation for the given value of the parameter. Print answers in the same order as values of $a$ appear in the input.

One can show that the number of solutions is always finite.


-----Example-----
Input
3
0
2
1073741823

Output
1
2
1073741824



-----Note-----

Let's define the bitwise exclusive OR (XOR) operation. Given two integers $x$ and $y$, consider their binary representations (possibly with leading zeroes): $x_k \dots x_2 x_1 x_0$ and $y_k \dots y_2 y_1 y_0$. Here, $x_i$ is the $i$-th bit of the number $x$ and $y_i$ is the $i$-th bit of the number $y$. Let $r = x \oplus y$ be the result of the XOR operation of $x$ and $y$. Then $r$ is defined as $r_k \dots r_2 r_1 r_0$ where:

$$ r_i = \left\{ \begin{aligned} 1, ~ \text{if} ~ x_i \ne y_i \\ 0, ~ \text{if} ~ x_i = y_i \end{aligned} \right. $$

For the first value of the parameter, only $x = 0$ is a solution of the equation.

For the second value of the parameter, solutions are $x = 0$ and $x = 2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr[], its starting position l and its ending position r. Sort the array using merge sort algorithm.
Example 1:
Input:
N = 5
arr[] = {4 1 3 9 7}
Output:
1 3 4 7 9
Example 2:
Input:
N = 10
arr[] = {10 9 8 7 6 5 4 3 2 1}
Output:
1 2 3 4 5 6 7 8 9 10
Your Task:
You don't need to take the input or print anything. Your task is to complete the function merge() which takes arr[], l, m, r as its input parameters and modifies arr[] in-place such that it is sorted from position l to position r, and function mergeSort() which uses merge() to sort the array in ascending order using merge sort algorithm.
Expected Time Complexity: O(nlogn) 
Expected Auxiliary Space: O(n)
Constraints:
1 <= N <= 10^{5}
1 <= arr[i] <= 10^{5}

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