vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Alice and Bob are playing a game. They have a tree consisting of n vertices. Initially, Bob has k chips, the i-th chip is located in the vertex a_i (all these vertices are unique). Before the game starts, Alice will place a chip into one of the vertices of the tree.

The game consists of turns. Each turn, the following events happen (sequentially, exactly in the following order):

  1. Alice either moves her chip to an adjacent vertex or doesn't move it; 
  2. for each Bob's chip, he either moves it to an adjacent vertex or doesn't move it. Note that this choice is done independently for each chip. 



The game ends when Alice's chip shares the same vertex with one (or multiple) of Bob's chips. Note that Bob's chips may share the same vertex, even though they are in different vertices at the beginning of the game.

Alice wants to maximize the number of turns, Bob wants to minimize it. If the game ends in the middle of some turn (Alice moves her chip to a vertex that contains one or multiple Bob's chips), this turn is counted.

For each vertex, calculate the number of turns the game will last if Alice places her chip in that vertex.

Input

The first line contains one integer n (2 ≤ n ≤ 2 ⋅ 10^5) — the number of vertices in the tree.

Then n - 1 lines follow, each line contains two integers u_i, v_i (1 ≤ u_i, v_i ≤ n; u_i ≠ v_i) that denote the endpoints of an edge. These edges form a tree.

The next line contains one integer k (1 ≤ k ≤ n - 1) — the number of Bob's chips.

The last line contains k integers a_1, a_2, ..., a_k (1 ≤ a_i ≤ n; a_i ≠ a_j if i ≠ j) — the vertices where the Bob's chips are initially placed.

Output

Print n integers. The i-th of them should be equal to the number of turns the game will last if Alice initially places her chip in the vertex i. If one of Bob's chips is already placed in vertex i, then the answer for vertex i is 0.

Examples

Input


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


Output


2 1 2 0 0


Input


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


Output


3 0 0 3 1 2 3 0


Input


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


Output


0 2 2 2 2 0 2 2 0 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You wrote down all integers from $0$ to $10^n - 1$, padding them with leading zeroes so their lengths are exactly $n$. For example, if $n = 3$ then you wrote out 000, 001, ..., 998, 999.

A block in an integer $x$ is a consecutive segment of equal digits that cannot be extended to the left or to the right.

For example, in the integer $00027734000$ there are three blocks of length $1$, one block of length $2$ and two blocks of length $3$.

For all integers $i$ from $1$ to $n$ count the number of blocks of length $i$ among the written down integers.

Since these integers may be too large, print them modulo $998244353$.


-----Input-----

The only line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$).


-----Output-----

In the only line print $n$ integers. The $i$-th integer is equal to the number of blocks of length $i$.

Since these integers may be too large, print them modulo $998244353$.


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

Output
10

Input
2

Output
180 10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
At many competitions that have a word «cup» in its official name the winner is presented with an actual cup. This time the organizers of one unusual programming competition have decided to please the winner even more and to add a nameplate to the cup with the handle of the winner.

The nameplate is to be rectangular and the text on it will be printed as a table of several rows and columns. Having some measurements done, the organizers have found out that the number a of rows cannot be greater than 5 while the number b of columns cannot exceed 20. Every cell of the table will contain either an asterisk («*») or a letter of user's handle.

Furthermore, the organizers want the rows of the table to be uniform, which means that the number of asterisks used in different rows should differ by at most one (i.e. you can't have two asterisks in the first row and none in the second). The main goal, however, is to obtain the winner's handle precisely when reading the table from top to bottom and from left to right in every row (skipping asterisks).

The organizers want for the nameplate to have as few rows as possible and among all valid tables with the minimum number of rows they want to choose the one that has the minimum number of columns.

The winner is not yet determined so your task is to write a program that, given a certain handle, generates the necessary table.

Input

The only line contains one string s (1 ≤ |s| ≤ 100), comprised of uppercase and lowercase Latin letters, — the handle of the winner.

Output

In the first line output the minimum number a of rows in the table and the minimum number b of columns in an optimal table with rows.

The following a lines should contain b characters each — any valid table.

Examples

Input


tourist


Output


1 7
tourist


Input


MyNameIsLifeIAmForeverByYourSideMyNameIsLife


Output


3 15
MyNameIsLifeIAm
ForeverByYourSi
deMyNameIsL*ife

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Squirrel Liss loves nuts. There are n trees (numbered 1 to n from west to east) along a street and there is a delicious nut on the top of each tree. The height of the tree i is h_{i}. Liss wants to eat all nuts.

Now Liss is on the root of the tree with the number 1. In one second Liss can perform one of the following actions:  Walk up or down one unit on a tree.  Eat a nut on the top of the current tree.  Jump to the next tree. In this action the height of Liss doesn't change. More formally, when Liss is at height h of the tree i (1 ≤ i ≤ n - 1), she jumps to height h of the tree i + 1. This action can't be performed if h > h_{i} + 1. 

Compute the minimal time (in seconds) required to eat all nuts.


-----Input-----

The first line contains an integer n (1  ≤  n ≤ 10^5) — the number of trees.

Next n lines contains the height of trees: i-th line contains an integer h_{i} (1 ≤ h_{i} ≤ 10^4) — the height of the tree with the number i.


-----Output-----

Print a single integer — the minimal time required to eat all nuts in seconds.


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

Output
5

Input
5
2
1
2
1
1

Output
14

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Many modern text editors automatically check the spelling of the user's text. Some editors even suggest how to correct typos.

In this problem your task to implement a small functionality to correct two types of typos in a word. We will assume that three identical letters together is a typo (for example, word "helllo" contains a typo). Besides, a couple of identical letters immediately followed by another couple of identical letters is a typo too (for example, words "helloo" and "wwaatt" contain typos).

Write a code that deletes the minimum number of letters from a word, correcting described typos in the word. You are allowed to delete letters from both ends and from the middle of the word.


-----Input-----

The single line of the input contains word s, its length is from 1 to 200000 characters. The given word s consists of lowercase English letters.


-----Output-----

Print such word t that it doesn't contain any typos described in the problem statement and is obtained from s by deleting the least number of letters.

If there are multiple solutions, print any of them.


-----Examples-----
Input
helloo

Output
hello

Input
woooooow

Output
woow



-----Note-----

The second valid answer to the test from the statement is "heloo".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to write a function which counts the number of squares contained in an ASCII art picture.

The input pictures contain rectangles---some of them squares---drawn with the characters `-`, `|`, and `+`, where `-` and `|` are used to represent horizontal and vertical sides, and `+` is used to represent corners and intersections. Each picture may contain multiple, possibly overlapping, rectangles.

A simple example input looks like this:

    +--+  +----+
    |  |  |    |    +-+
    |  |  +----+    | |
    +--+            +-+
    
There are two squares and one rectangle in this picture, so your function should return 2 for this input.

The following picture does not contain any squares, so the answer for this one is 0:

    +------+
    |      |
    +------+

Here is another, more complex input:

    +---+
    |   |
    | +-+-+
    | | | |
    +-+-+ |
      |   |
      +---+

The answer for this one is 3: two big squares, and a smaller square formed by the intersection of the two bigger ones. Similarly, the answer for the following picture is 5:

    +-+-+
    | | |
    +-+-+
    | | |
    +-+-+

You are going to implement a function `count_squares()` which takes an ASCII art picture as input and returns the number of squares the picture shows. The input to that function is an array of strings, where each string corresponds to a line of the ASCII art picture. Each string is guaranteed to contain only the characters `-`, `|`, `+`, and `` `` (space).

The smallest valid square has a side length of 2 and is represented by four `+` characters arranged in a square; a single `+` character is not considered a square.

Have fun!

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Vasya is very upset that many people on the Net mix uppercase and lowercase letters in one word. That's why he decided to invent an extension for his favorite browser that would change the letters' register in every word so that it either only consisted of lowercase letters or, vice versa, only of uppercase ones. At that as little as possible letters should be changed in the word. For example, the word HoUse must be replaced with house, and the word ViP — with VIP. If a word contains an equal number of uppercase and lowercase letters, you should replace all the letters with lowercase ones. For example, maTRIx should be replaced by matrix. Your task is to use the given method on one given word.

Input Specification:
The first line contains a word *s* — it consists of uppercase and lowercase Latin letters and possesses the length from 1 to 100.

Output Specification:
Print the corrected word *s*. If the given word *s* has strictly more uppercase letters, make the word written in the uppercase register, otherwise - in the lowercase one.

Demo Input:
['HoUse\n', 'ViP\n', 'maTRIx\n']

Demo Output:
['house\n', 'VIP\n', 'matrix\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We call a string good, if after merging all the consecutive equal characters, the resulting string is palindrome. For example, "aabba" is good, because after the merging step it will become "aba".

Given a string, you have to find two values:

  1. the number of good substrings of even length; 
  2. the number of good substrings of odd length. 

Input

The first line of the input contains a single string of length n (1 ≤ n ≤ 105). Each character of the string will be either 'a' or 'b'.

Output

Print two space-separated integers: the number of good substrings of even length and the number of good substrings of odd length.

Examples

Input

bb


Output

1 2


Input

baab


Output

2 4


Input

babb


Output

2 5


Input

babaa


Output

2 7

Note

In example 1, there are three good substrings ("b", "b", and "bb"). One of them has even length and two of them have odd length.

In example 2, there are six good substrings (i.e. "b", "a", "a", "b", "aa", "baab"). Two of them have even length and four of them have odd length.

In example 3, there are seven good substrings (i.e. "b", "a", "b", "b", "bb", "bab", "babb"). Two of them have even length and five of them have odd length.

Definitions

A substring s[l, r] (1 ≤ l ≤ r ≤ n) of string s = s1s2... sn is string slsl + 1... sr.

A string s = s1s2... sn is a palindrome if it is equal to string snsn - 1... s1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Slightly Decreasing Permutations

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Permutation *p* is an ordered set of integers *p*1,<=<=*p*2,<=<=...,<=<=*p**n*, consisting of *n* distinct positive integers, each of them doesn't exceed *n*. We'll denote the *i*-th element of permutation *p* as *p**i*. We'll call number *n* the size or the length of permutation *p*1,<=<=*p*2,<=<=...,<=<=*p**n*.

The decreasing coefficient of permutation *p*1,<=*p*2,<=...,<=*p**n* is the number of such *i* (1<=≤<=*i*<=&lt;<=*n*), that *p**i*<=&gt;<=*p**i*<=+<=1.

You have numbers *n* and *k*. Your task is to print the permutation of length *n* with decreasing coefficient *k*.

Input Specification:
The single line contains two space-separated integers: *n*,<=*k* (1<=≤<=*n*<=≤<=105,<=0<=≤<=*k*<=&lt;<=*n*) — the permutation length and the decreasing coefficient.

Output Specification:
In a single line print *n* space-separated integers: *p*1,<=*p*2,<=...,<=*p**n* — the permutation of length *n* with decreasing coefficient *k*. 

If there are several permutations that meet this condition, print any of them. It is guaranteed that the permutation with the sought parameters exists.

Demo Input:
['5 2\n', '3 0\n', '3 2\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A water company is trying to provide water from its pumping station to a mansion. The company owns $n$ water stations, numbered $1 \ldots n$, which are connected by a variety of pipes. Water can flow through both directions of a pipe, but the total amount of water that can flow through the pipe is bounded by the capacity of the pipe.

The water company is constantly improving the pipes, increasing the capacity of various pipes. The water company is conducting $k$ improvements (each of which is permanent after it is executed). An improvement consists of taking a pipe between two locations and increasing its capacity by a fixed amount, or installing a pipe between two locations which are not directly connected by a pipe.

After each improvement, the water company wants to know the maximum amount of water the mansion could receive.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains three integers, $n$ ($2 \le n \le 100$), $p$ ($0 \le p \le \frac{n (n-1)}{2}$), and $k$ ($1 \le k \le 10000$), where $n$ is the number of stations, $p$ is the number of initial pipes, and $k$ is the number of improvements. The first station in the list is always the pumping station, and the second is always the mansion.

The next $p$ lines will describe the pipes in the initial setup. The lines will each contain three integers, $a$, $b$ ($1 \le a < b \le n$) and $c$ ($1 \le c \le 1000$), which indicates that stations $a$ and $b$ are connected by a pipe with capacity $c$. No $(a, b)$ pair will appear more than once in this section.

The next $k$ lines will describe the improvements. The lines will each contain three integers, $a$, $b$ ($1 \le a < b \le n$) and $c$ ($1 \le c \le 1000$), which indicates that the pipe connecting stations $a$ and $b$ has its capacity increased by $c$ (if there is currently no pipe between $a$ and $b$, then one is created with capacity $c$). Note that it is possible for an $(a,b)$ pair to be repeated in this section.

-----Output-----
Output $k+1$ integers, each on its own line, describing the maximum amount of water that can reach the mansion. The first number is the amount of water reaching the mansion in the initial configuration. The next $k$ numbers are the amounts of water reaching the mansion after each improvement.

-----Examples-----
Sample Input:
3 2 1
1 3 10
2 3 1
2 3 15
Sample Output:
1
10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Æsir - CHAOS Æsir - V.

"Everything has been planned out. No more hidden concerns. The condition of Cytus is also perfect.

The time right now...... 00:01:12......

It's time."

The emotion samples are now sufficient. After almost 3 years, it's time for Ivy to awake her bonded sister, Vanessa.

The system inside A.R.C.'s Library core can be considered as an undirected graph with infinite number of processing nodes, numbered with all positive integers ($1, 2, 3, \ldots$). The node with a number $x$ ($x > 1$), is directly connected with a node with number $\frac{x}{f(x)}$, with $f(x)$ being the lowest prime divisor of $x$.

Vanessa's mind is divided into $n$ fragments. Due to more than 500 years of coma, the fragments have been scattered: the $i$-th fragment is now located at the node with a number $k_i!$ (a factorial of $k_i$).

To maximize the chance of successful awakening, Ivy decides to place the samples in a node $P$, so that the total length of paths from each fragment to $P$ is smallest possible. If there are multiple fragments located at the same node, the path from that node to $P$ needs to be counted multiple times.

In the world of zeros and ones, such a requirement is very simple for Ivy. Not longer than a second later, she has already figured out such a node.

But for a mere human like you, is this still possible?

For simplicity, please answer the minimal sum of paths' lengths from every fragment to the emotion samples' assembly node $P$.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 10^6$) — number of fragments of Vanessa's mind.

The second line contains $n$ integers: $k_1, k_2, \ldots, k_n$ ($0 \le k_i \le 5000$), denoting the nodes where fragments of Vanessa's mind are located: the $i$-th fragment is at the node with a number $k_i!$.


-----Output-----

Print a single integer, denoting the minimal sum of path from every fragment to the node with the emotion samples (a.k.a. node $P$).

As a reminder, if there are multiple fragments at the same node, the distance from that node to $P$ needs to be counted multiple times as well.


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

Output
5

Input
4
3 1 4 4

Output
6

Input
4
3 1 4 1

Output
6

Input
5
3 1 4 1 5

Output
11



-----Note-----

Considering the first $24$ nodes of the system, the node network will look as follows (the nodes $1!$, $2!$, $3!$, $4!$ are drawn bold):

[Image]

For the first example, Ivy will place the emotion samples at the node $1$. From here:

  The distance from Vanessa's first fragment to the node $1$ is $1$.  The distance from Vanessa's second fragment to the node $1$ is $0$.  The distance from Vanessa's third fragment to the node $1$ is $4$. 

The total length is $5$.

For the second example, the assembly node will be $6$. From here:

  The distance from Vanessa's first fragment to the node $6$ is $0$.  The distance from Vanessa's second fragment to the node $6$ is $2$.  The distance from Vanessa's third fragment to the node $6$ is $2$.  The distance from Vanessa's fourth fragment to the node $6$ is again $2$. 

The total path length is $6$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have two integers: A and B.
Print the largest number among A + B, A - B, and A \times B.

-----Constraints-----
 - All values in input are integers.
 - -100 \leq A,\ B \leq 100

-----Input-----
Input is given from Standard Input in the following format:
A B

-----Output-----
Print the largest number among A + B, A - B, and A \times B.

-----Sample Input-----
-13 3

-----Sample Output-----
-10

The largest number among A + B = -10, A - B = -16, and A \times B = -39 is -10.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
During the programming classes Vasya was assigned a difficult problem. However, he doesn't know how to code and was unable to find the solution in the Internet, so he asks you to help.

You are given a sequence $a$, consisting of $n$ distinct integers, that is used to construct the binary search tree. Below is the formal description of the construction process.
 1.  First element $a_1$ becomes the root of the tree. 1.  Elements $a_2, a_3, \ldots, a_n$ are added one by one. To add element $a_i$ one needs to traverse the tree starting from the root and using the following rules:   The pointer to the current node is set to the root. 1.  If $a_i$ is greater than the value in the current node, then its right child becomes the current node. Otherwise, the left child of the current node becomes the new current node. 1.  If at some point there is no required child, the new node is created, it is assigned value $a_i$ and becomes the corresponding child of the current node.

Input Specification:
The first line of the input contains a single integer $n$ ($2 \leq n \leq 100\,000$) — the length of the sequence $a$.

The second line contains $n$ distinct integers $a_i$ ($1 \leq a_i \leq 10^9$) — the sequence $a$ itself.

Output Specification:
Output $n - 1$ integers. For all $i &gt; 1$ print the value written in the node that is the parent of the node with value $a_i$ in it.

Demo Input:
['3\n1 2 3\n', '5\n4 2 3 1 6\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string str. Calculate the total number of unique substrings of the given string.
Example 1:
Input:
abd
Ouput:
6
Explanation:
str = abd. The 6 unique substrings 
are {a, b, d, ab, bd, abd}.
Example 2:
Input:
jaja
Ouput:
7
Explanation:
str = jaja. The substrings will be j, a, j, a, 
ja, aj, ja, jaj, aja, jaja. Out of these the 
unique are j, a, ja, aj, jaj, aja, jaja.
User Task:
You need to complete the function unique_substring() that takes str as a parameter and returns the count of unique substrings.
Constraints:
1 <= |str| <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A plot of land can be described by $M x N$ dots such that horizontal and vertical distance between any two dots is 10m.
Mr. Wolf would like to build a house in the land such that all four sides of the house are equal. Help Mr. Wolf to find the total number of unique positions where houses can be built. Two positions are different if and only if their sets of four dots are different.

-----Input:-----
The first line of the input gives the number of test cases, $T$. $T$ lines follow. Each line has two integers $M$ and $N$: the number of dots in each row and column of the plot, respectively.

-----Output:-----
For each test case, output one single integer containing the total number of different positions where the house can be built.

-----Constraints-----
- $1 \leq T \leq 100$
- $2 \leq M \leq 10^9$
- $2 \leq N \leq 10^9$

-----Sample Input:-----
4

2 4

3 4

4 4

1000 500  

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

10

20

624937395  

-----EXPLANATION:-----
Map 1

Map 2

Map 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:


Input: nums = [1,3], n = 6
Output: 1 
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:


Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].


Example 3:


Input: nums = [1,2,2], n = 5
Output: 0

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