Problem Statement

There are four types of oysters, labeled 1, 2, 3, and 4. Exactly one of these types causes stomach trouble if eaten. The other types do not cause stomach trouble when eaten.

Takahashi ate oysters 1 and 2, and Aoki ate oysters 1 and 3. The information on whether each person got sick is given as two strings S_1 and S_2. Specifically, S_1 = sick means Takahashi got sick, and S_1 = fine means Takahashi did not get sick. Likewise, S_2 = sick means Aoki got sick, and S_2 = fine means Aoki did not get sick.

Based on the given information, find which type of oyster causes stomach trouble.

Constraints

• Each of S_1 and S_2 is sick or fine.

Sample Input 1

sick fine

Sample Output 1

2

Takahashi (who ate oysters 1 and 2) got sick, and Aoki (who ate oysters 1 and 3) did not get sick, so it can be concluded that oyster 2 causes stomach trouble.

Sample Input 2

fine fine

Sample Output 2

4

Neither Takahashi (who ate oysters 1 and 2) nor Aoki (who ate oysters 1 and 3) got sick, so it can be concluded that oyster 4 causes stomach trouble.

Problem Statement

The magnitude of an earthquake is a logarithmic scale of the energy released by the earthquake. It is known that each time the magnitude increases by 1, the amount of energy gets multiplied by approximately 32.
Here, we assume that the amount of energy gets multiplied by exactly 32 each time the magnitude increases by 1. In this case, how many times is the amount of energy of a magnitude A earthquake as much as that of a magnitude B earthquake?

Constraints

• 3\leq B\leq A\leq 9
• A and B are integers.

Sample Input 1

6 4

Sample Output 1

1024

6 is 2 greater than 4, so a magnitude 6 earthquake has 32\times 32=1024 times as much energy as a magnitude 4 earthquake has.

Sample Input 2

5 5

Sample Output 2

1

Earthquakes with the same magnitude have the same amount of energy.

Problem Statement

A string S is said to be a substring of a string T when there is a pair of integers i and j (1 \leq i \leq j \leq |T|) that satisfy the following condition.

• The extraction of the i-th through j-th characters of T without changing the order equals S.

Let T be the concatenation of 10^5 copies of oxx.
Given a string S, print Yes if S is a substring of T, and No otherwise.

Constraints

• S is a string consisting of o and x.
• The length of S is between 1 and 10 (inclusive).

Sample Input 1

xoxxoxxo

Sample Output 1

Yes

T begins like this: oxxoxxoxxoxx... Since the extraction of 3-rd through 10-th characters of T equals S, S is a substring of T, so Yes should be printed.

Sample Input 2

xxoxxoxo

Sample Output 2

No

Since there is no way to extract from T a string that equals S, S is not a substring of T, so No should be printed.

Sample Input 3

ox

Sample Output 3

Yes

Problem Statement

You are given two strings S and T consisting of lowercase English letters. Determine if S is a prefix of T.

Constraints

• S and T are strings of lengths between 1 and 100 (inclusive) consisting of lowercase English letters.

Sample Input 1

atco
atcoder

Sample Output 1

Yes

atco is a prefix of atcoder. Thus, Yes should be printed.

Sample Input 2

code
atcoder

Sample Output 2

No

code is not a prefix of atcoder. Thus, No should be printed.

Sample Input 3

abc
abc

Sample Output 3

Yes

Note that a string is also a prefix of itself.

Sample Input 4

aaaa
aa

Sample Output 4

No

Problem Statement

Takahashi sent a string T consisting of lowercase English letters to Aoki. As a result, Aoki received a string T' consisting of lowercase English letters.

T' may have been altered from T. Specifically, exactly one of the following four conditions is known to hold.

• T' is equal to T.
• T' is a string obtained by inserting one lowercase English letter at one position (possibly the beginning and end) in T.
• T' is a string obtained by deleting one character from T.
• T' is a string obtained by changing one character in T to another lowercase English letter.

You are given the string T' received by Aoki and N strings S_1, S_2, \ldots, S_N consisting of lowercase English letters. Find all the strings among S_1, S_2, \ldots, S_N that could equal the string T sent by Takahashi.

Constraints

• N is an integer.
• 1 \leq N \leq 5 \times 10^5
• S_i and T' are strings of length between 1 and 5 \times 10^5, inclusive, consisting of lowercase English letters.
• The total length of S_1, S_2, \ldots, S_N is at most 5 \times 10^5.

Sample Input 1

5 ababc
ababc
babc
abacbc
abdbc
abbac

Sample Output 1

4
1 2 3 4

Among S_1, S_2, \ldots, S_5, the strings that could be equal to T are S_1, S_2, S_3, S_4, as explained below.

• S_1 could be equal to T, because T' = ababc is equal to S_1 = ababc.
• S_2 could be equal to T, because T' = ababc is obtained by inserting the letter a at the beginning of S_2 = babc.
• S_3 could be equal to T, because T' = ababc is obtained by deleting the fourth character c from S_3 = abacbc.
• S_4 could be equal to T, because T' = ababc is obtained by changing the third character d in S_4 = abdbc to b.
• S_5 could not be equal to T, because if we take S_5 = abbac as T, then T' = ababc does not satisfy any of the four conditions in the problem statement.

Sample Input 2

1 aoki
takahashi

Sample Output 2

0

Sample Input 3

9 atcoder
atoder
atcode
athqcoder
atcoder
tacoder
jttcoder
atoder
atceoder
atcoer

Sample Output 3

6
1 2 4 7 8 9

Problem Statement

We will call a sequence of length N where each of 1,2,\dots,N occurs once as a permutation of length N.
Given a permutation of length N, P = (p_1, p_2,\dots,p_N), print a permutation of length N, Q = (q_1,\dots,q_N), that satisfies the following condition.

• For every i (1 \leq i \leq N), the p_i-th element of Q is i.

It can be proved that there exists a unique Q that satisfies the condition.

Constraints

• 1 \leq N \leq 2 \times 10^5
• (p_1,p_2,\dots,p_N) is a permutation of length N (defined in Problem Statement).
• All values in input are integers.

Sample Input 1

3
2 3 1

Sample Output 1

3 1 2

The permutation Q=(3,1,2) satisfies the condition, as follows.

• For i = 1, we have p_i = 2, q_2 = 1.
• For i = 2, we have p_i = 3, q_3 = 2.
• For i = 3, we have p_i = 1, q_1 = 3.

Sample Input 2

3
1 2 3

Sample Output 2

1 2 3

If p_i = i for every i (1 \leq i \leq N), we will have P = Q.

Sample Input 3

5
5 3 2 4 1

Sample Output 3

5 3 2 4 1

Problem Statement

We have a tree with N vertices numbered 1, 2, \dots, N.
The i-th edge (1 \leq i \leq N - 1) connects Vertex u_i and Vertex v_i and has a weight w_i.

For different vertices u and v, let f(u, v) be the greatest weight of an edge contained in the shortest path from Vertex u to Vertex v.

Find \displaystyle \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^N f(i, j).

Constraints

• 2 \leq N \leq 10^5
• 1 \leq u_i, v_i \leq N
• 1 \leq w_i \leq 10^7
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

3
1 2 10
2 3 20

Sample Output 1

50

We have f(1, 2) = 10, f(2, 3) = 20, and f(1, 3) = 20, so we should print their sum, or 50.

Sample Input 2

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

Sample Output 2

76

Problem Statement

You are given a string S of length N consisting of 0 and 1. It describes a length-N sequence A=(A _ 1,A _ 2,\ldots,A _ N). If the i-th character of S (1\leq i\leq N) is 0, then A _ i=0; if it is 1, then A _ i=1.

Find the following:

\[\sum _ {1\leq i\leq j\leq N}(\cdots((A _ i\barwedge A _ {i+1})\barwedge A _ {i+2})\barwedge\cdots\barwedge A _ j)\]

More formally, find \displaystyle\sum _ {i=1} ^ {N}\sum _ {j=i} ^ Nf(i,j) for f(i,j)\ (1\leq i\leq j\leq N) defined as follows:

\[f(i,j)=\left\{\begin{matrix} A _ i&(i=j)\\ f(i,j-1)\barwedge A _ j\quad&(i\lt j) \end{matrix}\right.\]

Here, \barwedge, NAND, is a binary operator satisfying the following:

\[0\barwedge0=1,0\barwedge1=1,1\barwedge0=1,1\barwedge1=0.\]

Constraints

• 1\leq N\leq10^6
• S is a string of length N consisting of 0 and 1.
• All input values are integers.

Sample Input 1

5
00110

Sample Output 1

9

Here are the values of f(i,j) for the pairs (i,j) such that 1\leq i\leq j\leq N:

• f(1,1)=0=0
• f(1,2)=0\barwedge0=1
• f(1,3)=(0\barwedge0)\barwedge1=0
• f(1,4)=((0\barwedge0)\barwedge1)\barwedge1=1
• f(1,5)=(((0\barwedge0)\barwedge1)\barwedge1)\barwedge0=1
• f(2,2)=0=0
• f(2,3)=0\barwedge1=1
• f(2,4)=(0\barwedge1)\barwedge1=0
• f(2,5)=((0\barwedge1)\barwedge1)\barwedge0=1
• f(3,3)=1=1
• f(3,4)=1\barwedge1=0
• f(3,5)=(1\barwedge1)\barwedge0=1
• f(4,4)=1=1
• f(4,5)=1\barwedge0=1
• f(5,5)=0=0

Their sum is 0+1+0+1+1+0+1+0+1+1+0+1+1+1+0=9, so print 9.

Note that \barwedge does not satisfy the associative property. For instance, (1\barwedge1)\barwedge0=0\barwedge0=1\neq0=1\barwedge1=1\barwedge(1\barwedge0).

Sample Input 2

30
101010000100101011010011000010

Sample Output 2

326

Problem Statement

ABC 250 is a commemorable quarter milestone for Takahashi, who aims to hold ABC 1000, so he is going to celebrate this contest by eating as close to 1/4 of a pizza he bought as possible.

The pizza that Takahashi bought has a planar shape of convex N-gon. When the pizza is placed on an xy-plane, the i-th vertex has coordinates (X_i, Y_i).

Takahashi has decided to cut and eat the pizza as follows.

• First, Takahashi chooses two non-adjacent vertices from the vertices of the pizza and makes a cut with a knife along the line passing through those two points, dividing the pizza into two pieces.
• Then, he chooses one of the pieces at his choice and eats it.

Let a be the quarter (=1/4) of the area of the pizza that Takahashi bought, and b be the area of the piece of pizza that Takahashi eats. Find the minimum possible value of 8 \times |a-b|. We can prove that this value is always an integer.

Constraints

• All values in input are integers.
• 4 \le N \le 10^5
• |X_i|, |Y_i| \le 4 \times 10^8
• The given points are the vertices of a convex N-gon in the counterclockwise order.

Sample Input 1

5
3 0
2 3
-1 3
-3 1
-1 -1

Sample Output 1

1

Suppose that he makes a cut along the line passing through the 3-rd and the 5-th vertex and eats the piece containing the 4-th vertex.
Then, a=\frac{33}{2} \times \frac{1}{4} = \frac{33}{8}, b=4, and 8 \times |a-b|=1, which is minimum possible.

Sample Input 2

4
400000000 400000000
-400000000 400000000
-400000000 -400000000
400000000 -400000000

Sample Output 2

1280000000000000000

Sample Input 3

6
-816 222
-801 -757
-165 -411
733 131
835 711
-374 979

Sample Output 3

157889