Problem Statement

There are N squares arranged in a row, numbered 1, 2, ..., N from left to right. You are given a string S of length N consisting of . and #. If the i-th character of S is #, Square i contains a rock; if the i-th character of S is ., Square i is empty.

In the beginning, Snuke stands on Square A, and Fnuke stands on Square B.

You can repeat the following operation any number of times:

• Choose Snuke or Fnuke, and make him jump one or two squares to the right. The destination must be one of the squares, and it must not contain a rock or the other person.

You want to repeat this operation so that Snuke will stand on Square C and Fnuke will stand on Square D.

Determine whether this is possible.

Constraints

• 4 \leq N \leq 200\ 000
• S is a string of length N consisting of . and #.
• 1 \leq A, B, C, D \leq N
• Square A, B, C and D do not contain a rock.
• A, B, C and D are all different.
• A < B
• A < C
• B < D

Sample Input 1

7 1 3 6 7
.#..#..

Sample Output 1

Yes

The objective is achievable by, for example, moving the two persons as follows. (A and B represent Snuke and Fnuke, respectively.)

A#B.#..

A#.B#..

.#AB#..

.#A.#B.

.#.A#B.

.#.A#.B

.#..#AB

Sample Input 2

7 1 3 7 6
.#..#..

Sample Output 2

No

Sample Input 3

15 1 3 15 13
...#.#...#.#...

Sample Output 3

Yes

Problem Statement

You are given a string s consisting of A, B and C.

Snuke wants to perform the following operation on s as many times as possible:

• Choose a contiguous substring of s that reads ABC and replace it with BCA.

Find the maximum possible number of operations.

Constraints

• 1 \leq |s| \leq 200000
• Each character of s is A, B and C.

Sample Input 1

ABCABC

Sample Output 1

3

You can perform the operations three times as follows: ABCABC → BCAABC → BCABCA → BCBCAA. This is the maximum result.

Sample Input 2

C

Sample Output 2

0

Sample Input 3

ABCACCBABCBCAABCB

Sample Output 3

6

Problem Statement

Takahashi and Aoki will take N exams numbered 1 to N. They have decided to compete in these exams. The winner will be determined as follows:

• For each exam i, Takahashi decides its importance c_i, which must be an integer between l_i and u_i (inclusive).

• Let A be \sum_{i=1}^{N} c_i \times (Takahashi's score on Exam i), and B be \sum_{i=1}^{N} c_i \times (Aoki's score on Exam i). Takahashi wins if A \geq B, and Aoki wins if A < B.

Takahashi knows that Aoki will score b_i on Exam i, with his supernatural power.

Takahashi himself, on the other hand, will score 0 on all the exams without studying more. For each hour of study, he can increase his score on some exam by 1. (He can only study for an integer number of hours.) However, he cannot score more than X on an exam, since the perfect score for all the exams is X.

Print the minimum number of study hours required for Takahashi to win.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq X \leq 10^5
• 0 \leq b_i \leq X (1 \leq i \leq N)
• 1 \leq l_i \leq u_i \leq 10^5 (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

2 100
85 2 3
60 1 1

Sample Output 1

115

One optimal strategy is as follows:

• Choose c_1 = 3, c_2 = 1.

• Study to score 100 on Exam 1 and 15 on Exam 2.

Then, A = 3 \times 100 + 1 \times 15 = 315, B = 3 \times 85 + 1 \times 60 = 315 and Takahashi will win.

Sample Input 2

2 100
85 2 3
60 10 10

Sample Output 2

77

Sample Input 3

1 100000
31415 2718 2818

Sample Output 3

31415

Sample Input 4

10 1000
451 4593 6263
324 310 6991
378 1431 7068
71 1757 9218
204 3676 4328
840 6221 9080
684 1545 8511
709 5467 8674
862 6504 9835
283 4965 9980

Sample Output 4

2540

Problem Statement

Snuke is playing with red and blue balls, placing them on a two-dimensional plane.

First, he performed N operations to place red balls. In the i-th of these operations, he placed RC_i red balls at coordinates (RX_i,RY_i). Then, he performed another N operations to place blue balls. In the i-th of these operations, he placed BC_i blue balls at coordinates (BX_i,BY_i). The total number of red balls placed and the total number of blue balls placed are equal, that is, \sum_{i=1}^{N} RC_i = \sum_{i=1}^{N} BC_i. Let this value be S.

Snuke will now form S pairs of red and blue balls so that every ball belongs to exactly one pair. Let us define the score of a pair of a red ball at coordinates (rx, ry) and a blue ball at coordinates (bx, by) as |rx-bx| + |ry-by|.

Snuke wants to maximize the sum of the scores of the pairs. Help him by finding the maximum possible sum of the scores of the pairs.

Constraints

• 1 \leq N \leq 1000
• 0 \leq RX_i,RY_i,BX_i,BY_i \leq 10^9
• 1 \leq RC_i,BC_i \leq 10
• \sum_{i=1}^{N} RC_i = \sum_{i=1}^{N} BC_i
• All values in input are integers.

Sample Input 1

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

Sample Output 1

8

If we pair the red ball at coordinates (0,0) and the blue ball at coordinates (2,2), the score of this pair is |0-2| + |0-2|=4. Then, if we pair the red ball at coordinates (3,2) and the blue ball at coordinates (5,0), the score of this pair is |3-5| + |2-0|=4. Making these two pairs results in the total score of 8, which is the maximum result.

Sample Input 2

3
0 0 1
2 2 1
0 0 2
1 1 1
1 1 1
3 3 2

Sample Output 2

16

Snuke may have performed multiple operations at the same coordinates.

Sample Input 3

10
582463373 690528069 8
621230322 318051944 4
356524296 974059503 6
372751381 111542460 9
392867214 581476334 6
606955458 513028121 5
882201596 791660614 9
250465517 91918758 3
618624774 406956634 6
426294747 736401096 5
974896051 888765942 5
726682138 336960821 3
715144179 82444709 6
599055841 501257806 6
390484433 962747856 4
912334580 219343832 8
570458984 648862300 6
638017635 572157978 10
435958984 585073520 7
445612658 234265014 6

Sample Output 3

45152033546

Problem Statement

You are given a tree with N vertices numbered 1, 2, ..., N. The i-th edge connects Vertex a_i and Vertex b_i. You are also given a string S of length N consisting of 0 and 1. The i-th character of S represents the number of pieces placed on Vertex i.

Snuke will perform the following operation some number of times:

• Choose two pieces the distance between which is at least 2, and bring these pieces closer to each other by 1. More formally, choose two vertices u and v, each with one or more pieces, and consider the shortest path between them. Here the path must contain at least two edges. Then, move one piece from u to its adjacent vertex on the path, and move one piece from v to its adjacent vertex on the path.

By repeating this operation, Snuke wants to have all the pieces on the same vertex. Is this possible? If the answer is yes, also find the minimum number of operations required to achieve it.

Constraints

• 2 \leq N \leq 2000
• |S| = N
• S consists of 0 and 1, and contains at least one 1.
• 1 \leq a_i, b_i \leq N(a_i \neq b_i)
• The edges (a_1, b_1), (a_2, b_2), ..., (a_{N - 1}, b_{N - 1}) forms a tree.

Sample Input 1

7
0010101
1 2
2 3
1 4
4 5
1 6
6 7

Sample Output 1

3

We can gather all the pieces in three operations as follows:

• Choose the pieces on Vertex 3 and 5.
• Choose the pieces on Vertex 2 and 7.
• Choose the pieces on Vertex 4 and 6.

Sample Input 2

7
0010110
1 2
2 3
1 4
4 5
1 6
6 7

Sample Output 2

-1

Sample Input 3

2
01
1 2

Sample Output 3

0

Problem Statement

Snuke found a random number generator. It generates an integer between 0 and 2^N-1 (inclusive). An integer sequence A_0, A_1, \cdots, A_{2^N-1} represents the probability that each of these integers is generated. The integer i (0 \leq i \leq 2^N-1) is generated with probability A_i / S, where S = \sum_{i=0}^{2^N-1} A_i. The process of generating an integer is done independently each time the generator is executed.

Snuke has an integer X, which is now 0. He can perform the following operation any number of times:

• Generate an integer v with the generator and replace X with X \oplus v, where \oplus denotes the bitwise XOR.

For each integer i (0 \leq i \leq 2^N-1), find the expected number of operations until X becomes i, and print it modulo 998244353. More formally, represent the expected number of operations as an irreducible fraction P/Q. Then, there exists a unique integer R such that R \times Q \equiv P \mod 998244353,\ 0 \leq R < 998244353, so print this R.

We can prove that, for every i, the expected number of operations until X becomes i is a finite rational number, and its integer representation modulo 998244353 can be defined.

Constraints

• 1 \leq N \leq 18
• 1 \leq A_i \leq 1000
• All values in input are integers.

Sample Input 1

2
1 1 1 1

Sample Output 1

0
4
4
4

X=0 after zero operations, so the expected number of operations until X becomes 0 is 0.

Also, from any state, the value of X after one operation is 0, 1, 2 or 3 with equal probability. Thus, the expected numbers of operations until X becomes 1, 2 and 3 are all 4.

Sample Input 2

2
1 2 1 2

Sample Output 2

0
499122180
4
499122180

The expected numbers of operations until X becomes 0, 1, 2 and 3 are 0, 7/2, 4 and 7/2, respectively.

Sample Input 3

4
337 780 799 10 796 875 331 223 941 67 148 483 390 565 116 355

Sample Output 3

0
468683018
635850749
96019779
657074071
24757563
745107950
665159588
551278361
143136064
557841197
185790407
988018173
247117461
129098626
789682908