Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N consisting of non-negative integers.

Determine if there is an even number represented as the sum of two different elements of A. If it exists, find the maximum such number.

Constraints

• 2\leq N \leq 2\times 10^5
• 0\leq A_i\leq 10^9
• The elements of A are distinct.
• All values in the input are integers.

Sample Input 1

3
2 3 4

Sample Output 1

6

The values represented as the sum of two distinct elements of A are 5, 6, and 7. We have an even number here, and the maximum is 6.

Sample Input 2

2
1 0

Sample Output 2

-1

The value represented as the sum of two distinct elements of A is 1. We have no even number here, so -1 should be printed.

Problem Statement

A single-player card game is popular in AtCoder Inc. Each card in the game has a lowercase English letter or the symbol @ written on it. There is plenty number of cards for each kind. The game goes as follows.

1. Arrange the same number of cards in two rows.
2. Replace each card with @ with one of the following cards: a, t, c, o, d, e, r.
3. If the two rows of cards coincide, you win. Otherwise, you lose.

To win this game, you will do the following cheat.

• Freely rearrange the cards within a row whenever you want after step 1.

You are given two strings S and T, representing the two rows you have after step 1. Determine whether it is possible to win with cheating allowed.

Constraints

• S and T consist of lowercase English letters and @.
• The lengths of S and T are equal and between 1 and 2\times 10^5, inclusive.

Sample Input 1

ch@ku@ai
choku@@i

Sample Output 1

Yes

You can replace the @s so that both rows become chokudai.

Sample Input 2

ch@kud@i
akidu@ho

Sample Output 2

Yes

You can cheat and replace the @s so that both rows become chokudai.

Sample Input 3

aoki
@ok@

Sample Output 3

No

You cannot win even with cheating.

Sample Input 4

aa
bb

Sample Output 4

No

Problem Statement

You are given a weighted undirected complete graph with N vertices numbered from 1 to N. The edge connecting vertices i and j (i< j) has a weight of D_{i,j}.

When choosing some number of edges under the following condition, find the maximum possible total weight of the chosen edges.

• The endpoints of the chosen edges are pairwise distinct.

Constraints

• 2\leq N\leq 16
• 1\leq D_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

4
1 5 4
7 8
6

Sample Output 1

13

If you choose the edge connecting vertices 1 and 3, and the edge connecting vertices 2 and 4, the total weight of the edges is 5+8=13.

It can be shown that this is the maximum achievable value.

Sample Input 2

3
1 2
3

Sample Output 2

3

N can be odd.

Sample Input 3

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

Sample Output 3

75

Problem Statement

There is an undirected graph with N vertices numbered 1 through N, and initially with 0 edges.
Given Q queries, process them in order. After processing each query, print the number of vertices that are not connected to any other vertices by an edge.

The i-th query, \mathrm{query}_i, is of one of the following two kinds.

• 1 u v: connect vertex u and vertex v with an edge. It is guaranteed that, when this query is given, vertex u and vertex v are not connected by an edge.

• 2 v: remove all edges that connect vertex v and the other vertices. (Vertex v itself is not removed.)

Constraints

• 2 \leq N\leq 3\times 10^5
• 1 \leq Q\leq 3\times 10^5
• For each query of the first kind, 1\leq u,v\leq N and u\neq v.
• For each query of the second kind, 1\leq v\leq N.
• Right before a query of the first kind is given, there is no edge between vertices u and v.
• All values in the input are integers.

Sample Input 1

3 7
1 1 2
1 1 3
1 2 3
2 1
1 1 2
2 2
1 1 2

Sample Output 1

1
0
0
1
0
3
1

After the first query, vertex 1 and vertex 2 are connected to each other by an edge, but vertex 3 is not connected to any other vertices.
Thus, 1 should be printed in the first line.

After the third query, all pairs of different vertices are connected by an edge.
However, the fourth query asks to remove all edges that connect vertex 1 and the other vertices, specifically to remove the edge between vertex 1 and vertex 2, and another between vertex 1 and vertex 3. As a result, vertex 2 and vertex 3 are connected to each other, while vertex 1 is not connected to any other vertices by an edge.
Thus, 0 and 1 should be printed in the third and fourth lines, respectively.

Sample Input 2

2 1
2 1

Sample Output 2

2

When the query of the second kind is given, there may be no edge that connects that vertex and the other vertices.

Problem Statement

Given is a string S consisting of digits from 1 through 9.
From this string S, let us make a formula T by the following operations.

• Initially, let T=S.
• Choose a (possibly empty) set A of different integers where each element is between 1 and |S|-1 (inclusive).
• For each element x in descending order, do the following.
  • Insert a + between the x-th and (x+1)-th characters of T.

For example, when S= 1234 and A= \lbrace 2,3 \rbrace, we will have T= 12+3+4.

Consider evaluating all possible formulae T obtained by these operations. Find the sum, modulo 998244353, of the evaluations.

Constraints

• 1 \le |S| \le 2 \times 10^5
• S consists of 1, 2, 3, 4, 5, 6, 7, 8, and 9.

Sample Input 1

1234

Sample Output 1

1736

There are eight formulae that can be obtained as T: 1234, 123+4, 12+34, 12+3+4, 1+234, 1+23+4, 1+2+34, and 1+2+3+4.
The sum of the evaluations of these formulae is 1736.

Sample Input 2

1

Sample Output 2

1

S may have a length of 1, in which case the only possible choice for A is the empty set.

Sample Input 3

31415926535897932384626433832795

Sample Output 3

85607943

Be sure to find the sum modulo 998244353.