vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
This problem differs from the next one only in the presence of the constraint on the equal length of all numbers $a_1, a_2, \dots, a_n$. Actually, this problem is a subtask of the problem D2 from the same contest and the solution of D2 solves this subtask too.

A team of SIS students is going to make a trip on a submarine. Their target is an ancient treasure in a sunken ship lying on the bottom of the Great Rybinsk sea. Unfortunately, the students don't know the coordinates of the ship, so they asked Meshanya (who is a hereditary mage) to help them. He agreed to help them, but only if they solve his problem.

Let's denote a function that alternates digits of two numbers $f(a_1 a_2 \dots a_{p - 1} a_p, b_1 b_2 \dots b_{q - 1} b_q)$, where $a_1 \dots a_p$ and $b_1 \dots b_q$ are digits of two integers written in the decimal notation without leading zeros.

In other words, the function $f(x, y)$ alternately shuffles the digits of the numbers $x$ and $y$ by writing them from the lowest digits to the older ones, starting with the number $y$. The result of the function is also built from right to left (that is, from the lower digits to the older ones). If the digits of one of the arguments have ended, then the remaining digits of the other argument are written out. Familiarize with examples and formal definitions of the function below.

For example: $$f(1111, 2222) = 12121212$$ $$f(7777, 888) = 7787878$$ $$f(33, 44444) = 4443434$$ $$f(555, 6) = 5556$$ $$f(111, 2222) = 2121212$$

Formally,  if $p \ge q$ then $f(a_1 \dots a_p, b_1 \dots b_q) = a_1 a_2 \dots a_{p - q + 1} b_1 a_{p - q + 2} b_2 \dots a_{p - 1} b_{q - 1} a_p b_q$;  if $p < q$ then $f(a_1 \dots a_p, b_1 \dots b_q) = b_1 b_2 \dots b_{q - p} a_1 b_{q - p + 1} a_2 \dots a_{p - 1} b_{q - 1} a_p b_q$. 

Mishanya gives you an array consisting of $n$ integers $a_i$. All numbers in this array are of equal length (that is, they consist of the same number of digits). Your task is to help students to calculate $\sum_{i = 1}^{n}\sum_{j = 1}^{n} f(a_i, a_j)$ modulo $998\,244\,353$.


-----Input-----

The first line of the input contains a single integer $n$ ($1 \le n \le 100\,000$) — the number of elements in the array. The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array. All numbers $a_1, a_2, \dots, a_n$ are of equal length (that is, they consist of the same number of digits).


-----Output-----

Print the answer modulo $998\,244\,353$.


-----Examples-----
Input
3
12 33 45

Output
26730
Input
2
123 456

Output
1115598
Input
1
1

Output
11
Input
5
1000000000 1000000000 1000000000 1000000000 1000000000

Output
265359409

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarpus got hold of a family tree. The found tree describes the family relations of n people, numbered from 1 to n. Every person in this tree has at most one direct ancestor. Also, each person in the tree has a name, the names are not necessarily unique.

We call the man with a number a a 1-ancestor of the man with a number b, if the man with a number a is a direct ancestor of the man with a number b.

We call the man with a number a a k-ancestor (k > 1) of the man with a number b, if the man with a number b has a 1-ancestor, and the man with a number a is a (k - 1)-ancestor of the 1-ancestor of the man with a number b.

In the tree the family ties do not form cycles. In other words there isn't a person who is his own direct or indirect ancestor (that is, who is an x-ancestor of himself, for some x, x > 0).

We call a man with a number a the k-son of the man with a number b, if the man with a number b is a k-ancestor of the man with a number a.

Polycarpus is very much interested in how many sons and which sons each person has. He took a piece of paper and wrote m pairs of numbers vi, ki. Help him to learn for each pair vi, ki the number of distinct names among all names of the ki-sons of the man with number vi.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 105) — the number of people in the tree. Next n lines contain the description of people in the tree. The i-th line contains space-separated string si and integer ri (0 ≤ ri ≤ n), where si is the name of the man with a number i, and ri is either the number of the direct ancestor of the man with a number i or 0, if the man with a number i has no direct ancestor. 

The next line contains a single integer m (1 ≤ m ≤ 105) — the number of Polycarpus's records. Next m lines contain space-separated pairs of integers. The i-th line contains integers vi, ki (1 ≤ vi, ki ≤ n).

It is guaranteed that the family relationships do not form cycles. The names of all people are non-empty strings, consisting of no more than 20 lowercase English letters.

Output

Print m whitespace-separated integers — the answers to Polycarpus's records. Print the answers to the records in the order, in which the records occur in the input.

Examples

Input

6
pasha 0
gerald 1
gerald 1
valera 2
igor 3
olesya 1
5
1 1
1 2
1 3
3 1
6 1


Output

2
2
0
1
0


Input

6
valera 0
valera 1
valera 1
gerald 0
valera 4
kolya 4
7
1 1
1 2
2 1
2 2
4 1
5 1
6 1


Output

1
0
0
0
2
0
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nura wants to buy k gadgets. She has only s burles for that. She can buy each gadget for dollars or for pounds. So each gadget is selling only for some type of currency. The type of currency and the cost in that currency are not changing.

Nura can buy gadgets for n days. For each day you know the exchange rates of dollar and pound, so you know the cost of conversion burles to dollars or to pounds.

Each day (from 1 to n) Nura can buy some gadgets by current exchange rate. Each day she can buy any gadgets she wants, but each gadget can be bought no more than once during n days.

Help Nura to find the minimum day index when she will have k gadgets. Nura always pays with burles, which are converted according to the exchange rate of the purchase day. Nura can't buy dollars or pounds, she always stores only burles. Gadgets are numbered with integers from 1 to m in order of their appearing in input.


-----Input-----

First line contains four integers n, m, k, s (1 ≤ n ≤ 2·10^5, 1 ≤ k ≤ m ≤ 2·10^5, 1 ≤ s ≤ 10^9) — number of days, total number and required number of gadgets, number of burles Nura has.

Second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^6) — the cost of one dollar in burles on i-th day.

Third line contains n integers b_{i} (1 ≤ b_{i} ≤ 10^6) — the cost of one pound in burles on i-th day.

Each of the next m lines contains two integers t_{i}, c_{i} (1 ≤ t_{i} ≤ 2, 1 ≤ c_{i} ≤ 10^6) — type of the gadget and it's cost. For the gadgets of the first type cost is specified in dollars. For the gadgets of the second type cost is specified in pounds.


-----Output-----

If Nura can't buy k gadgets print the only line with the number -1.

Otherwise the first line should contain integer d — the minimum day index, when Nura will have k gadgets. On each of the next k lines print two integers q_{i}, d_{i} — the number of gadget and the day gadget should be bought. All values q_{i} should be different, but the values d_{i} can coincide (so Nura can buy several gadgets at one day). The days are numbered from 1 to n.

In case there are multiple possible solutions, print any of them.


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

Output
3
1 1
2 3

Input
4 3 2 200
69 70 71 72
104 105 106 107
1 1
2 2
1 2

Output
-1

Input
4 3 1 1000000000
900000 910000 940000 990000
990000 999000 999900 999990
1 87654
2 76543
1 65432

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given postorder traversal of a Binary Search Tree, you need to construct a BST from postorder traversal. The output will be inorder traversal of the constructed BST.
 
Example 1:
Input:
6
1 7 5 50 40 10
Output:
1 5 7 10 40 50
Explanation:
Testcase 1: The BST for the given post order traversal is:
Thus the inorder traversal of BST is: 1 5 7 10 40 50.
 
Your Task:
The task is to complete the function constructTree() which takes an array post[], size as as the argument and returns the root of BST. 
 
Expected Time Complexity: O(No. of  nodes in BST)
Expected Auxiliary Space: O(No. of  nodes in BST)
 
Constraints:
1 <= T <= 100
1 <= N <= 200

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
Kevin and Stuart want to play the 'The Minion Game'.

Game Rules

Both players are given the same string, S.
Both players have to make substrings using the letters of the string S.
Stuart has to make words starting with consonants.
Kevin has to make words starting with vowels.
The game ends when both players have made all possible substrings.

Scoring
A player gets +1 point for each occurrence of the substring in the string S.

=====Example=====
String S = BANANA
Kevin's vowel beginning word = ANA
Here, ANA occurs twice in BANANA. Hence, Kevin will get 2 Points.

Your task is to determine the winner of the game and their score.

=====Input Format=====
A single line of input containing the string S.
Note: The string S will contain only uppercase letters: [A-Z].

=====Constraints=====
0 < len(S) < 10^6

=====Output Format=====
Print one line: the name of the winner and their score separated by a space.
If the game is a draw, print Draw.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the Pradnya Planet, there are n aliens which have different powers.
The aliens are numbered from A1 to An, and their respective powers are denoted
from P1 to Pn. Now, these aliens have to fight against another planet for d days.
For each day, either of these 2 situations can occur:
1. If situation is 'C' 
Any two aliens from range Al to Ar will have to fight against another planet
(The resultant power of the 2 aliens fighting will be the product of their individual powers)

2. If situation is 'P' 
An alien Ai changes its power to p

Now, Yash Lahoti being the "Big Boss" of these n aliens, needs to make sure that the 
2 aliens going on any day produce the maximum power. Help Rushabh determine the maximum
power which can be produced each day.
Input Format:
First line contains two space separated integers n and d, denoting the number of aliens and number of days.
Each of the next n lines contains the power of the n respective aliens

Each of the next d lines can contain 3 space separated inputs of two types:
Type 1: 'C'       l           r
    where 'C' represents the situation, 
l and r represents the range of aliens Al to Ar, out of which any two can go to fight.

Type 2: 'P'          i            p
    where 'P' represents the situaton, 
i and p represent that the power of alien Ai becomes p
Output Format:
For each of the situation of type 'P', output a single line one integer deonting the maximum power which 
can be produced by any of the 2 aliens from range (Al to Ar).
Constraints:
2 ≤ n ≤ 10^5
-4*10^4 ≤ P1, P2 ,...Pn ≤ 4*10^4
1 ≤ d ≤ 10^6
1 ≤ l < r ≤n
1 ≤ i ≤ n
-4*10^4 ≤ p ≤ 4*10^4

SAMPLE INPUT
5 3
-4 1 3 4 -2
C 1 3
P 4 -4
C 1 4

SAMPLE OUTPUT
3
16

Explanation

For the first day, aliens with powers 1 and 3(A2 and A3) will give maximum power = 3

For the second day, the power of A4 will change to -4
Thus the powers of aliens will now be: -4, 1, 3, -4, -2

For the third day, 1st and 4th alien(A1 and A4) with powers -4 and -4 will give maximum power=16

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Berland year consists of $m$ months with $d$ days each. Months are numbered from $1$ to $m$. Berland week consists of $w$ days. The first day of the year is also the first day of the week. Note that the last week of the year might be shorter than $w$ days.

A pair $(x, y)$ such that $x < y$ is ambiguous if day $x$ of month $y$ is the same day of the week as day $y$ of month $x$.

Count the number of ambiguous pairs.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.

Each of the next $t$ lines contains three integers $m$, $d$ and $w$ ($1 \le m, d, w \le 10^9$) — the number of months in a year, the number of days in a month and the number of days in a week.


-----Output-----

Print $t$ integers — for each testcase output the number of pairs $(x, y)$ such that $x < y$ and day $x$ of month $y$ is the same day of the week as day $y$ of month $x$.


-----Example-----
Input
5
6 7 4
10 7 12
12 30 7
1 1 1
3247834 10298779 625324

Output
6
9
5
0
116461800



-----Note-----

Here are the pairs for the first test case:  $$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N points numbered 1 to N arranged in a line in this order.

Takahashi decides to make an undirected graph, using these points as the vertices. In the beginning, the graph has no edge. Takahashi will do M operations to add edges in this graph. The i-th operation is as follows:

* The operation uses integers L_i and R_i between 1 and N (inclusive), and a positive integer C_i. For every pair of integers (s, t) such that L_i \leq s < t \leq R_i, add an edge of length C_i between Vertex s and Vertex t.



The integers L_1, ..., L_M, R_1, ..., R_M, C_1, ..., C_M are all given as input.

Takahashi wants to solve the shortest path problem in the final graph obtained. Find the length of the shortest path from Vertex 1 to Vertex N in the final graph.

Constraints

* 2 \leq N \leq 10^5
* 1 \leq M \leq 10^5
* 1 \leq L_i < R_i \leq N
* 1 \leq C_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N M
L_1 R_1 C_1
:
L_M R_M C_M


Output

Print the length of the shortest path from Vertex 1 to Vertex N in the final graph. If there is no shortest path, print `-1` instead.

Examples

Input

4 3
1 3 2
2 4 3
1 4 6


Output

5


Input

4 2
1 2 1
3 4 2


Output

-1


Input

10 7
1 5 18
3 4 8
1 3 5
4 7 10
5 9 8
6 10 5
8 10 3


Output

28

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
When Kefa came to the restaurant and sat at a table, the waiter immediately brought him the menu. There were *n* dishes. Kefa knows that he needs exactly *m* dishes. But at that, he doesn't want to order the same dish twice to taste as many dishes as possible. 

Kefa knows that the *i*-th dish gives him *a**i* units of satisfaction. But some dishes do not go well together and some dishes go very well together. Kefa set to himself *k* rules of eating food of the following type — if he eats dish *x* exactly before dish *y* (there should be no other dishes between *x* and *y*), then his satisfaction level raises by *c*. 

Of course, our parrot wants to get some maximal possible satisfaction from going to the restaurant. Help him in this hard task!

Input Specification:
The first line of the input contains three space-separated numbers, *n*, *m* and *k* (1<=≤<=*m*<=≤<=*n*<=≤<=18, 0<=≤<=*k*<=≤<=*n*<=*<=(*n*<=-<=1)) — the number of dishes on the menu, the number of portions Kefa needs to eat to get full and the number of eating rules.

The second line contains *n* space-separated numbers *a**i*, (0<=≤<=*a**i*<=≤<=109) — the satisfaction he gets from the *i*-th dish.

Next *k* lines contain the rules. The *i*-th rule is described by the three numbers *x**i*, *y**i* and *c**i* (1<=≤<=*x**i*,<=*y**i*<=≤<=*n*, 0<=≤<=*c**i*<=≤<=109). That means that if you eat dish *x**i* right before dish *y**i*, then the Kefa's satisfaction increases by *c**i*. It is guaranteed that there are no such pairs of indexes *i* and *j* (1<=≤<=*i*<=&lt;<=*j*<=≤<=*k*), that *x**i*<==<=*x**j* and *y**i*<==<=*y**j*.

Output Specification:
In the single line of the output print the maximum satisfaction that Kefa can get from going to the restaurant.

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

Demo Output:
['3\n', '12\n']

Note:
In the first sample it is best to first eat the second dish, then the first one. Then we get one unit of satisfaction for each dish and plus one more for the rule.

In the second test the fitting sequences of choice are 4 2 1 or 2 1 4. In both cases we get satisfaction 7 for dishes and also, if we fulfill rule 1, we get an additional satisfaction 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string of characters, find the length of the longest proper prefix which is also a proper suffix.
NOTE: Prefix and suffix can be overlapping but they should not be equal to the entire string.
Example 1:
Input: s = "abab"
Output: 2
Explanation: "ab" is the longest proper 
prefix and suffix. 
Example 2:
Input: s = "aaaa"
Output: 3
Explanation: "aaa" is the longest proper 
prefix and suffix. 
Your task:
You do not need to read any input or print anything. The task is to complete the function lps(), which takes a string as input and returns an integer. 
Expected Time Complexity: O(|s|)
Expected Auxiliary Space: O(|s|)
Constraints:
1 ≤ |s| ≤ 10^{5}
s contains lower case English alphabets

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Bear and Up-Down

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The life goes up and down, just like nice sequences. Sequence *t*1,<=*t*2,<=...,<=*t**n* is called nice if the following two conditions are satisfied: 
 -  *t**i*<=&lt;<=*t**i*<=+<=1 for each odd *i*<=&lt;<=*n*; -  *t**i*<=&gt;<=*t**i*<=+<=1 for each even *i*<=&lt;<=*n*. 
For example, sequences (2,<=8), (1,<=5,<=1) and (2,<=5,<=1,<=100,<=99,<=120) are nice, while (1,<=1), (1,<=2,<=3) and (2,<=5,<=3,<=2) are not.

Bear Limak has a sequence of positive integers *t*1,<=*t*2,<=...,<=*t**n*. This sequence is not nice now and Limak wants to fix it by a single swap. He is going to choose two indices *i*<=&lt;<=*j* and swap elements *t**i* and *t**j* in order to get a nice sequence. Count the number of ways to do so. Two ways are considered different if indices of elements chosen for a swap are different.

Input Specification:
The first line of the input contains one integer *n* (2<=≤<=*n*<=≤<=150<=000) — the length of the sequence.

The second line contains *n* integers *t*1,<=*t*2,<=...,<=*t**n* (1<=≤<=*t**i*<=≤<=150<=000) — the initial sequence. It's guaranteed that the given sequence is not nice.

Output Specification:
Print the number of ways to swap two elements exactly once in order to get a nice sequence.

Demo Input:
['5\n2 8 4 7 7\n', '4\n200 150 100 50\n', '10\n3 2 1 4 1 4 1 4 1 4\n', '9\n1 2 3 4 5 6 7 8 9\n']

Demo Output:
['2\n', '1\n', '8\n', '0\n']

Note:
In the first sample, there are two ways to get a nice sequence with one swap: 
 1.  Swap *t*<sub class="lower-index">2</sub> = 8 with *t*<sub class="lower-index">4</sub> = 7. 1.  Swap *t*<sub class="lower-index">1</sub> = 2 with *t*<sub class="lower-index">5</sub> = 7. 
In the second sample, there is only one way — Limak should swap *t*<sub class="lower-index">1</sub> = 200 with *t*<sub class="lower-index">4</sub> = 50.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer `n`, find two integers `a` and `b` such that:
```Pearl
A) a >= 0 and b >= 0
B) a + b = n
C) DigitSum(a) + Digitsum(b) is maximum of all possibilities.  
```
You will return the digitSum(a) + digitsum(b). 

```
For example:
solve(29) = 11. If we take 15 + 14 = 29 and digitSum = 1 + 5 + 1 + 4 = 11. There is no larger outcome.
```
`n` will not exceed `10e10`.

More examples in test cases. 

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Forward, march!

Time Limit: 1 seconds

Memory Limit: 64 megabytes

Problem Description:
Jack has become a soldier now. Unfortunately, he has trouble with the drill. Instead of marching beginning with the left foot and then changing legs with each step, as ordered, he keeps repeating a sequence of steps, in which he sometimes makes the wrong steps or — horror of horrors! — stops for a while. For example, if Jack uses the sequence 'right, left, break', when the sergeant yells: 'Left! Right! Left! Right! Left! Right!', Jack first makes a step with the right foot, then one with the left foot, then he is confused and stops for a moment, then again - this time according to the order - starts with the right foot, then uses the left foot, then - to the sergeant's irritation - he stops to catch his breath, to incorrectly start with the right foot again... Marching this way, Jack will make the step that he is supposed to in the given moment in only one third of cases.

When the officers convinced him he should do something about it, Jack decided to modify the basic sequence of steps that he repeats. However, in order not to get too tired, he has decided that the only thing he'll do is adding any number of breaks in any positions of the original sequence (a break corresponds to stopping for the duration of one step). Of course, Jack can't make a step on the same foot twice in a row, if there is no pause between these steps. It is, however, not impossible that the sequence of steps he used so far is incorrect (it would explain a lot, actually).

Help Private Jack! Given the sequence of steps he keeps repeating, calculate the maximal percentage of time that he can spend marching correctly after adding some breaks to his scheme.

Input Specification:
The first line of input contains a sequence consisting only of characters 'L', 'R' and 'X', where 'L' corresponds to a step with the left foot, 'R' — with the right foot, and 'X' — to a break. The length of the sequence will not exceed 106.

Output Specification:
Output the maximum percentage of time that Jack can spend marching correctly, rounded down to exactly six digits after the decimal point.

Demo Input:
['X\n', 'LXRR\n']

Demo Output:
['0.000000\n', '50.000000\n']

Note:
In the second example, if we add two breaks to receive LXXRXR, Jack will march: LXXRXRLXXRXRL... instead of LRLRLRLRLRLRL... and will make the correct step in half the cases. If we didn't add any breaks, the sequence would be incorrect — Jack can't step on his right foot twice in a row.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Restoration of the Permutation

Time Limit: 1 seconds

Memory Limit: 256 megabytes

Problem Description:
Let *A*<==<={*a*1,<=*a*2,<=...,<=*a**n*} be any permutation of the first *n* natural numbers {1,<=2,<=...,<=*n*}. You are given a positive integer *k* and another sequence *B*<==<={*b*1,<=*b*2,<=...,<=*b**n*}, where *b**i* is the number of elements *a**j* in *A* to the left of the element *a**t*<==<=*i* such that *a**j*<=≥<=(*i*<=+<=*k*).

For example, if *n*<==<=5, a possible *A* is {5,<=1,<=4,<=2,<=3}. For *k*<==<=2, *B* is given by {1,<=2,<=1,<=0,<=0}. But if *k*<==<=3, then *B*<==<={1,<=1,<=0,<=0,<=0}.

For two sequences *X*<==<={*x*1,<=*x*2,<=...,<=*x**n*} and *Y*<==<={*y*1,<=*y*2,<=...,<=*y**n*}, let *i*-th elements be the first elements such that *x**i*<=≠<=*y**i*. If *x**i*<=&lt;<=*y**i*, then *X* is lexicographically smaller than *Y*, while if *x**i*<=&gt;<=*y**i*, then *X* is lexicographically greater than *Y*.

Given *n*, *k* and *B*, you need to determine the lexicographically smallest *A*.

Input Specification:
The first line contains two space separated integers *n* and *k* (1<=≤<=*n*<=≤<=1000, 1<=≤<=*k*<=≤<=*n*). On the second line are *n* integers specifying the values of *B*<==<={*b*1,<=*b*2,<=...,<=*b**n*}.

Output Specification:
Print on a single line *n* integers of *A*<==<={*a*1,<=*a*2,<=...,<=*a**n*} such that *A* is lexicographically minimal. It is guaranteed that the solution exists.

Demo Input:
['5 2\n1 2 1 0 0\n', '4 2\n1 0 0 0\n']

Demo Output:
['4 1 5 2 3 ', '2 3 1 4 ']

Note:
none

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