The Fair Nut lives in $$$n$$$ story house. $$$a_i$$$ people live on the $$$i$$$-th floor of the house. Every person uses elevator twice a day: to get from the floor where he/she lives to the ground (first) floor and to get from the first floor to the floor where he/she lives, when he/she comes back home in the evening.
It was decided that elevator, when it is not used, will stay on the $$$x$$$-th floor, but $$$x$$$ hasn't been chosen yet. When a person needs to get from floor $$$a$$$ to floor $$$b$$$, elevator follows the simple algorithm:
- Moves from the $$$x$$$-th floor (initially it stays on the $$$x$$$-th floor) to the $$$a$$$-th and takes the passenger.
- Moves from the $$$a$$$-th floor to the $$$b$$$-th floor and lets out the passenger (if $$$a$$$ equals $$$b$$$, elevator just opens and closes the doors, but still comes to the floor from the $$$x$$$-th floor).
- Moves from the $$$b$$$-th floor back to the $$$x$$$-th.
Your task is to help Nut to find the minimum number of electricity units, that it would be enough for one day, by choosing an optimal the $$$x$$$-th floor. Don't forget than elevator initially stays on the $$$x$$$-th floor.
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the number of floors.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 100$$$) — the number of people on each floor.
In a single line, print the answer to the problem — the minimum number of electricity units.
3
0 2 1
16
2
1 1
4
In the first example, the answer can be achieved by choosing the second floor as the $$$x$$$-th floor. Each person from the second floor (there are two of them) would spend $$$4$$$ units of electricity per day ($$$2$$$ to get down and $$$2$$$ to get up), and one person from the third would spend $$$8$$$ units of electricity per day ($$$4$$$ to get down and $$$4$$$ to get up). $$$4 \cdot 2 + 8 \cdot 1 = 16$$$.
In the second example, the answer can be achieved by choosing the first floor as the $$$x$$$-th floor.
The Fair Nut likes kvass very much. On his birthday parents presented him $$$n$$$ kegs of kvass. There are $$$v_i$$$ liters of kvass in the $$$i$$$-th keg. Each keg has a lever. You can pour your glass by exactly $$$1$$$ liter pulling this lever. The Fair Nut likes this drink very much, so he wants to pour his glass by $$$s$$$ liters of kvass. But he wants to do it, so kvass level in the least keg is as much as possible.
Help him find out how much kvass can be in the least keg or define it's not possible to pour his glass by $$$s$$$ liters of kvass.
The first line contains two integers $$$n$$$ and $$$s$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le s \le 10^{12}$$$) — the number of kegs and glass volume.
The second line contains $$$n$$$ integers $$$v_1, v_2, \ldots, v_n$$$ ($$$1 \le v_i \le 10^9$$$) — the volume of $$$i$$$-th keg.
If the Fair Nut cannot pour his glass by $$$s$$$ liters of kvass, print $$$-1$$$. Otherwise, print a single integer — how much kvass in the least keg can be.
3 3
4 3 5
3
3 4
5 3 4
2
3 7
1 2 3
-1
In the first example, the answer is $$$3$$$, the Fair Nut can take $$$1$$$ liter from the first keg and $$$2$$$ liters from the third keg. There are $$$3$$$ liters of kvass in each keg.
In the second example, the answer is $$$2$$$, the Fair Nut can take $$$3$$$ liters from the first keg and $$$1$$$ liter from the second keg.
In the third example, the Fair Nut can't pour his cup by $$$7$$$ liters, so the answer is $$$-1$$$.
The Fair Nut found a string $$$s$$$. The string consists of lowercase Latin letters. The Nut is a curious guy, so he wants to find the number of strictly increasing sequences $$$p_1, p_2, \ldots, p_k$$$, such that:
- For each $$$i$$$ ($$$1 \leq i \leq k$$$), $$$s_{p_i} =$$$ 'a'.
- For each $$$i$$$ ($$$1 \leq i \lt k$$$), there is such $$$j$$$ that $$$p_i \lt j \lt p_{i + 1}$$$ and $$$s_j =$$$ 'b'.
The Nut is upset because he doesn't know how to find the number. Help him.
This number should be calculated modulo $$$10^9 + 7$$$.
The first line contains the string $$$s$$$ ($$$1 \leq |s| \leq 10^5$$$) consisting of lowercase Latin letters.
In a single line print the answer to the problem — the number of such sequences $$$p_1, p_2, \ldots, p_k$$$ modulo $$$10^9 + 7$$$.
abbaa
5
baaaa
4
agaa
3
In the first example, there are $$$5$$$ possible sequences. $$$[1]$$$, $$$[4]$$$, $$$[5]$$$, $$$[1, 4]$$$, $$$[1, 5]$$$.
In the second example, there are $$$4$$$ possible sequences. $$$[2]$$$, $$$[3]$$$, $$$[4]$$$, $$$[5]$$$.
In the third example, there are $$$3$$$ possible sequences. $$$[1]$$$, $$$[3]$$$, $$$[4]$$$.
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.
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.
Print one number — the maximum amount of gasoline that he can have at the end of the path.
3
1 3 3
1 2 2
1 3 2
3
5
6 3 2 5 0
1 2 10
2 3 3
2 4 1
1 5 1
7
The optimal way in the first example is $$$2 \to 1 \to 3$$$.
The optimal way in the second example is $$$2 \to 4$$$.
Recently, the Fair Nut has written $$$k$$$ strings of length $$$n$$$, consisting of letters "a" and "b". He calculated $$$c$$$ — the number of strings that are prefixes of at least one of the written strings. Every string was counted only one time.
Then, he lost his sheet with strings. He remembers that all written strings were lexicographically not smaller than string $$$s$$$ and not bigger than string $$$t$$$. He is interested: what is the maximum value of $$$c$$$ that he could get.
A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:
- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$, $$$1 \leq k \leq 10^9$$$).
The second line contains a string $$$s$$$ ($$$|s| = n$$$) — the string consisting of letters "a" and "b.
The third line contains a string $$$t$$$ ($$$|t| = n$$$) — the string consisting of letters "a" and "b.
It is guaranteed that string $$$s$$$ is lexicographically not bigger than $$$t$$$.
Print one number — maximal value of $$$c$$$.
2 4 aa bb
6
3 3 aba bba
8
4 5 abbb baaa
8
In the first example, Nut could write strings "aa", "ab", "ba", "bb". These $$$4$$$ strings are prefixes of at least one of the written strings, as well as "a" and "b". Totally, $$$6$$$ strings.
In the second example, Nut could write strings "aba", "baa", "bba".
In the third example, there are only two different strings that Nut could write. If both of them are written, $$$c=8$$$.
Once Grisha found a tree (connected graph without cycles) with a root in node $$$1$$$.
But this tree was not just a tree. A permutation $$$p$$$ of integers from $$$0$$$ to $$$n - 1$$$ is written in nodes, a number $$$p_i$$$ is written in node $$$i$$$.
As Grisha likes to invent some strange and interesting problems for himself, but not always can solve them, you need to help him deal with two types of queries on this tree.
Let's define a function $$$MEX(S)$$$, where $$$S$$$ is a set of non-negative integers, as a smallest non-negative integer that is not included in this set.
Let $$$l$$$ be a simple path in this tree. So let's define indices of nodes which lie on $$$l$$$ as $$$u_1$$$, $$$u_2$$$, $$$\ldots$$$, $$$u_k$$$.
Define $$$V(l)$$$ as a set {$$$p_{u_1}$$$, $$$p_{u_2}$$$, $$$\ldots$$$ , $$$p_{u_k}$$$}.
Then queries are:
- For two nodes $$$i$$$ and $$$j$$$, swap $$$p_i$$$ and $$$p_j$$$.
- Find the maximum value of $$$MEX(V(l))$$$ in all possible $$$l$$$.
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of nodes of a tree.
The second line contains $$$n$$$ integers — $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_n$$$ ($$$0\leq p_i \lt n$$$) — the permutation $$$p$$$, it's guaranteed that all numbers are different .
The third line contains $$$n - 1$$$ integers — $$$d_2$$$, $$$d_3$$$, $$$\ldots$$$, $$$d_n$$$ ($$$1 \leq d_i \lt i$$$), where $$$d_i$$$ is a direct ancestor of node $$$i$$$ in a tree.
The fourth line contains a single integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of queries.
The following $$$q$$$ lines contain the description of queries:
At the beginning of each of next $$$q$$$ lines, there is a single integer $$$t$$$ ($$$1$$$ or $$$2$$$) — the type of a query:
- If $$$t = 1$$$, the line also contains two integers $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \leq n$$$) — the indices of nodes, where values of the permutation should be swapped.
- If $$$t = 2$$$, you need to find the maximum value of $$$MEX(V(l))$$$ in all possible $$$l$$$.
For each type 2 query print a single integer — the answer for this query.
6 2 5 0 3 1 4 1 1 3 3 3 3 2 1 6 3 2
3 2
6 5 2 1 4 3 0 1 1 1 3 3 9 2 1 5 3 2 1 6 1 2 1 4 2 2 1 1 6 2
3 2 4 4 2
Number written in brackets is a permutation value of a node.
