Problem Statement

There is a programming contest with N problems. For each i = 1, 2, \ldots, N, the score for the i-th problem is S_i.

Print the total score for all problems with a score of X or less.

Constraints

• All input values are integers.
• 4 \leq N \leq 8
• 100 \leq S_i \leq 675
• 100 \leq X \leq 675

Sample Input 1

6 200
100 675 201 200 199 328

Sample Output 1

499

Three problems have a score of 200 or less: the first, fourth, and fifth, for a total score of S_1 + S_4 + S_5 = 100 + 200 + 199 = 499.

Sample Input 2

8 675
675 675 675 675 675 675 675 675

Sample Output 2

5400

Sample Input 3

8 674
675 675 675 675 675 675 675 675

Sample Output 3

0

Problem Statement

AtCoder Kingdom uses a calendar whose year has N months. Month i (1\leq i\leq N) has D _ i days, from day 1 of month i to day D _ i of month i.

How many days in a year of AtCoder have "repdigits" dates?

Here, day j of month i (1\leq i\leq N,1\leq j\leq D _ i) is said to have a repdigit date if and only if all digits in the decimal notations of i and j are the same.

Constraints

• 1\leq N\leq100
• 1\leq D _ i\leq100\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

12
31 29 31 30 31 30 31 31 30 31 30 31

Sample Output 1

13

In AtCoder Kingdom, the days that have repdigit dates are January 1, January 11, February 2, February 22, March 3, April 4, May 5, June 6, July 7, August 8, September 9, November 1, and November 11, for a total of 13 days.

Sample Input 2

10
10 1 2 3 4 5 6 7 8 100

Sample Output 2

1

In AtCoder Kingdom, only January 1 has a repdigit date.

Sample Input 3

30
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32

Sample Output 3

15

Problem Statement

You are given a string S = S_1S_2\ldots S_N of length N consisting of lowercase English letters.

Additionally, you are given Q queries about the string S. For i = 1, 2, \ldots, Q, the i-th query is represented by two integers l_i, r_i and asks the following.

In the substring S_{l_i}S_{l_i+1}\ldots S_{r_i} of S, which ranges from the l_i-th to the r_i-th character, how many places are there where the same lowercase English letter occurs twice in a row? In other words, how many integers p satisfy l_i \leq p \leq r_i-1 and S_p = S_{p+1}?

Print the answer for each of the Q queries.

Constraints

• N and Q are integers.
• 1 \leq N, Q \leq 3 \times 10^5
• S is a string of length N consisting of lowercase English letters.
• l_i and r_i are integers.
• 1 \leq l_i \leq r_i \leq N

Sample Input 1

11 4
mississippi
3 9
4 10
4 6
7 7

Sample Output 1

2
2
0
0

The answers to the four queries are as follows.

• For the first query, S_3S_4\ldots S_9 = ssissip has two places where the same lowercase English letter occurs twice in a row: S_3S_4 = ss and S_6S_7 = ss.
• For the second query, S_4S_5\ldots S_{10} = sissipp has two places where the same lowercase English letter occurs twice in a row: S_6S_7 = ss and S_9S_{10} = pp.
• For the third query, S_4S_5S_6 = sis has zero places where the same lowercase English letter occurs twice in a row.
• For the fourth query, S_7 = s has zero places where the same lowercase English letter occurs twice in a row.

Sample Input 2

5 1
aaaaa
1 5

Sample Output 2

4

S_1S_2\ldots S_5 = aaaaa has four places where the same lowercase English letter occurs twice in a row: S_1S_2 = aa, S_2S_3 = aa, S_3S_4 = aa, and S_4S_5 = aa.

Problem Statement

You are given a string S consisting of three different characters: A, B, and C.

As long as S contains the string ABC as a consecutive substring, repeat the following operation:

Remove the leftmost occurrence of the substring ABC from S.

Print the final string S after performing the above procedure.

Constraints

• S is a string of length between 1 and 2 \times 10^5, inclusive, consisting of the characters A, B, and C.

Sample Input 1

BAABCBCCABCAC

Sample Output 1

BCAC

For the given string S = BAABCBCCABCAC, the operations are performed as follows.

• In the first operation, the ABC from the 3-rd to the 5-th character in S = BAABCBCCABCAC is removed, resulting in S = BABCCABCAC.
• In the second operation, the ABC from the 2-nd to the 4-th character in S = BABCCABCAC is removed, resulting in S = BCABCAC.
• In the third operation, the ABC from the 3-rd to the 5-th character in S = BCABCAC is removed, resulting in S = BCAC.

Therefore, the final S is BCAC.

Sample Input 2

ABCABC

Sample Output 2

In this example, the final S is an empty string.

Sample Input 3

AAABCABCABCAABCABCBBBAABCBCCCAAABCBCBCC

Sample Output 3

AAABBBCCC

Problem Statement

You are given a weighted simple connected undirected graph with N vertices and M edges, where vertices are numbered 1 to N, and edges are numbered 1 to M. Additionally, a positive integer K is given.
Edge i\ (1\leq i\leq M) connects vertices u_i and v_i and has a weight of w_i.

For a spanning tree T of this graph, the cost of T is defined as the sum, modulo K, of the weights of the edges in T. Find the minimum cost of a spanning tree of this graph.

Constraints

• 2\leq N\leq8
• N-1\leq M\leq\dfrac{N(N-1)}2
• 1\leq K\leq10^{15}
• 1\leq u_i\lt v_i\leq N\ (1\leq i\leq M)
• 0\leq w_i\lt K\ (1\leq i\leq M)
• The given graph is simple and connected.
• All input values are integers.

Sample Input 1

5 6 328
1 2 99
1 3 102
2 3 86
2 4 94
2 5 95
3 4 81

Sample Output 1

33

The given graph is shown below:

The cost of the spanning tree containing edges 1,3,5,6 is (99+86+81+95)\bmod{328}=361\bmod{328}=33. The cost of every spanning tree of this graph is at least 33, so print 33.

Sample Input 2

6 5 998244353
1 2 337361568
1 6 450343304
2 3 61477244
2 5 745383438
4 5 727360840

Sample Output 2

325437688

Print the cost of the only spanning tree of this graph, which is 325437688.

Sample Input 3

8 28 936294041850197
1 2 473294720906780
1 3 743030800139244
1 4 709363019414774
1 5 383643612490312
1 6 557102781022861
1 7 623179288538138
1 8 739618599410809
2 3 857687812294404
2 4 893923168139714
2 5 581822471860662
2 6 740549363586558
2 7 307226438833222
2 8 447399029952998
3 4 636318083622768
3 5 44548707643622
3 6 307262781240755
3 7 12070267388230
3 8 700247263184082
4 5 560567890325333
4 6 704726113717147
4 7 588263818615687
4 8 549007536393172
5 6 779230871080408
5 7 825982583786498
5 8 713928998174272
6 7 751331074538826
6 8 449873635430228
7 8 11298381761479

Sample Output 3

11360716373

Note that the input and the answer may not fit into a 32\operatorname{bit} integer.

Problem Statement

You are given Q triples of integers (a_1, b_1, d_1), (a_2, b_2, d_2), \ldots, (a_Q, b_Q, d_Q).

A subset S of the set \lbrace 1, 2, \ldots, Q\rbrace is defined to be a good set if there exists an integer sequence (X_1, X_2, \ldots, X_N) of length N that satisfies:

X_{a_i} - X_{b_i} = d_i for all i \in S.

Starting with S as an empty set, perform the following operation for i = 1, 2, \ldots, Q in this order:

If S \cup \lbrace i \rbrace is a good set, then replace S with S \cup \lbrace i \rbrace.

Print all elements of the final set S in ascending order.

Constraints

• All input values are integers.
• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq a_i, b_i \leq N
• -10^9 \leq d_i \leq 10^9

Sample Input 1

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

Sample Output 1

1 2 4 5

Starting with S as an empty set, perform the operation described in the problem statement for i = 1, 2, 3, 4, 5 in this order, as follows.

• For i = 1, the set S \cup \lbrace i \rbrace = \lbrace 1 \rbrace is a good set, because (X_1, X_2, X_3) = (3, 1, 4) satisfies the condition in the problem statement, for example, so replace S with \lbrace 1\rbrace.
• For i = 2, the set S \cup \lbrace i \rbrace = \lbrace 1, 2 \rbrace is a good set, because (X_1, X_2, X_3) = (3, 1, -2) satisfies the condition in the problem statement, for example, so replace S with \lbrace 1, 2\rbrace.
• For i = 3, the set S \cup \lbrace i \rbrace = \lbrace 1, 2, 3 \rbrace is not a good set.
• For i = 4, the set S \cup \lbrace i \rbrace = \lbrace 1, 2, 4 \rbrace is a good set, because (X_1, X_2, X_3) = (3, 1, -2) satisfies the condition in the problem statement, for example, so replace S with \lbrace 1, 2, 4\rbrace.
• For i = 5, the set S \cup \lbrace i \rbrace = \lbrace 1, 2, 4, 5 \rbrace is a good set, because (X_1, X_2, X_3) = (3, 1, -2) satisfies the condition in the problem statement, for example, so replace S with \lbrace 1, 2, 4, 5\rbrace.

Therefore, the final set S is \lbrace 1, 2, 4, 5\rbrace.

Sample Input 2

200000 1
1 1 1

Sample Output 2

The final set S is empty.

Sample Input 3

5 20
4 2 125421359
2 5 -191096267
3 4 -42422908
3 5 -180492387
3 3 174861038
2 3 -82998451
3 4 -134761089
3 1 -57159320
5 2 191096267
2 4 -120557647
4 2 125421359
2 3 142216401
4 5 -96172984
3 5 -108097816
1 5 -50938496
1 2 140157771
5 4 65674908
4 3 35196193
4 4 0
3 4 188711840

Sample Output 3

1 2 3 6 8 9 11 14 15 16 17 19

Problem Statement

You are given two sequences of length N: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

You can perform the following two types of operations on the sequence A any number of times in any order.

• Split A at any positions and freely rearrange the split sequences. Each split position incurs a cost of C. More formally, at a cost of (X-1)C, take a sequence of length X+1, (i_0,i_1,i_2,\ldots,i_X)\ (0=i_0\lt i_1\lt i_2\lt\cdots\lt i_X=N), and a permutation p of (1,2,\ldots,X), and replace A with the concatenation of (A_{i_{p_j-1}+1},A_{i_{p_j-1}+2},\ldots,A_{i_{p_j}}) in ascending order of j.
• Choose an integer k and any element of A, and add k to the value of the chosen element, for a cost of |k|.

Find the minimum total cost required to make A and B equal by performing the operations.

Constraints

• 1\leq N\leq22
• 1\leq C\leq10^{15}
• 1\leq A_i\leq10^{15}\ (1\leq i\leq N)
• 1\leq B_i\leq10^{15}\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

5 1
3 1 4 1 5
9 2 6 5 3

Sample Output 1

12

For example, you can make A and B equal by performing the following operations.

• Add 2 to A_2. It costs 2, and A becomes (3,3,4,1,5).
• Add 1 to A_4. It costs 1, and A becomes (3,3,4,2,5).
• Add 3 to A_3. It costs 3, and A becomes (3,3,7,2,5).
• Split A into (3,3) and (7,2,5), and swap their order. It costs 1, and A becomes (7,2,5,3,3).
• Add 1 to A_3. It costs 1, and A becomes (7,2,6,3,3).
• Add 2 to A_4. It costs 2, and A becomes (7,2,6,5,3).
• Add 2 to A_1. It costs 2, and A becomes (9,2,6,5,3).

The total cost incurred is 2+1+3+1+1+2+2=12.

It is impossible to make A and B equal with a total cost of 11 or less, so print 12.

Sample Input 2

5 1000000000
3 1 4 1 5
9 2 6 5 3

Sample Output 2

15

For example, you can make A and B equal by performing the following operations.

• Add 6 to A_1. It costs 6, and A becomes (9,1,4,1,5).
• Add 1 to A_2. It costs 1, and A becomes (9,2,4,1,5).
• Add 2 to A_3. It costs 2, and A becomes (9,2,6,1,5).
• Add 4 to A_4. It costs 4, and A becomes (9,2,6,5,5).
• Add -2 to A_5. It costs 2, and A becomes (9,2,6,5,3).

The total cost incurred is 15.

It is impossible to make A and B equal with a total cost of 14 or less, so print 15.

Sample Input 3

22 467772225675200
814424018890229 837987908732596 281175505732576 405797525366223 319378664987871 305374284356649 519144936694626 316916938328237 590332737480143 506785561790072 945769796193819 365498597798550 5386616044591 672368930784037 478017750715806 340276460237787 176509793332130 2734777402752 677509027289850 250325127275409 260270543315523 103584313625431
720386673780641 77160494100361 540947273460639 255177791002759 969333325196025 477751866935037 369600749728569 466236682780196 343161112138696 541310338013515 42740499599240 165778332156355 618106559852784 16582487395877 591851763813728 221861304303645 982850624742022 728669467505250 337968530842725 746724490610504 61587851254728 451153536869240

Sample Output 3

4370668608634071

Note that the input and the answer may not fit into a 32\operatorname{bit} integer.