Problem Statement

The AtCoder Restaurant uses N types of ingredients numbered from 1 to N.

The restaurant offers M dishes numbered from 1 to M. Dish i uses K_i types of ingredients, namely A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}.

Snuke currently dislikes all N ingredients. He cannot eat any dish that uses one or more ingredients he dislikes, and he can eat a dish that uses none of the disliked ingredients.

Over the next N days, he will overcome his dislikes one ingredient per day. On day i, he overcomes ingredient B_i, and from then on he no longer dislikes it.

For each i=1,2,\ldots,N, find:

• the number of dishes at the AtCoder Restaurant that he can eat immediately after overcoming ingredient B_i on day i.

Constraints

• 1 \leq N \leq 3 \times 10^{5}
• 1 \leq M \leq 3 \times 10^{5}
• 1 \leq K_i \leq N (1 \leq i \leq M)
• The sum of K_i is at most 3 \times 10^{5}.
• 1 \leq A_{i,j} \leq N (1 \leq i \leq M, 1 \leq j \leq K_i)
• A_{i,j} \neq A_{i,k} (1 \leq i \leq M, j \neq k)
• 1 \leq B_i \leq N (1 \leq i \leq N)
• B_i \neq B_j (i \neq j )
• All input values are integers.

Sample Input 1

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

Sample Output 1

0
1
2
3
4

Snuke overcomes his disliked ingredients as follows:

• Day 1: He overcomes ingredient 1. At this time, every dish still uses a disliked ingredient, so print 0.
• Day 2: He overcomes ingredient 3. Dish 4 no longer uses any disliked ingredient and becomes edible; all other dishes still use disliked ingredients, so print 1.
• Day 3: He overcomes ingredient 2. Dish 1 no longer uses any disliked ingredient and becomes edible; all dishes except 1 and 4 still use disliked ingredients, so print 2.
• Day 4: He overcomes ingredient 5. Dish 3 no longer uses any disliked ingredient and becomes edible; all dishes except 1, 3, and 4 still use disliked ingredients, so print 3.
• Day 5: He overcomes ingredient 4. Dish 2 no longer uses any disliked ingredient and becomes edible; now all dishes have no disliked ingredients, so print 4.

Sample Input 2

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

Sample Output 2

0
0
1
1
1
2
4
6
8

Problem Statement

There is a slot machine with N reels.
The placement of symbols on the i-th reel is represented by a string S_i of length 10 containing each of 0, 1, \ldots, 9 exactly once.

Each reel has a corresponding button. For each non-negative integer t, Takahashi can press one of the buttons of his choice (or do nothing) t seconds after the reels start spinning.
If the button for the i-th reel is pressed t seconds after the start of the spin, the i-th reel will stop to display the ((t\bmod{10})+1)-th character of S_i.
Here, t\bmod{10} denotes the remainder when t is divided by 10.

Takahashi wants to stop all reels to make them display the same character.
Find the minimum number of seconds needed to achieve his objective after the start of the spin.

Constraints

• 2\leq N\leq 100
• N is an integer.
• S_i is a string of length 10 containing each of 0, 1, \ldots, 9 exactly once.

Sample Input 1

3
1937458062
8124690357
2385760149

Sample Output 1

6

Takahashi can make all reels display 8 in 6 seconds after the start of the spin by stopping them as follows.

• 0 seconds after the start of the spin, press the button for the 2-nd reel, making it stop to display the ((0\bmod{10})+1=1)-st character of S_2, 8.
• 2 seconds after the start of the spin, press the button for the 3-rd reel, making it stop to display the ((2\bmod{10})+1=3)-rd character of S_3, 8.
• 6 seconds after the start of the spin, press the button for the 1-st reel, making it stop to display the ((6\bmod{10})+1=7)-th character of S_1, 8.

There is no way to make all reels display the same character in five seconds or less, so the answer is 6.

Sample Input 2

5
0123456789
0123456789
0123456789
0123456789
0123456789

Sample Output 2

40

Note that he must stop all reels to make them display the same character.

Problem Statement

You are given a simple undirected graph G with N vertices and M edges (a simple graph does not contain self-loops or multi-edges). For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i.

Print the number of pairs of integers (u, v) that satisfy 1 \leq u \lt v \leq N and both of the following conditions.

• The graph G does not have an edge connecting vertex u and vertex v.
• Adding an edge connecting vertex u and vertex v in the graph G results in a bipartite graph.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min \lbrace 2 \times 10^5, N(N-1)/2 \rbrace
• 1 \leq u_i, v_i \leq N
• The graph G is simple.
• All values in the input are integers.

Sample Input 1

5 4
4 2
3 1
5 2
3 2

Sample Output 1

2

We have two pairs of integers (u, v) that satisfy the conditions in the problem statement: (1, 4) and (1, 5). Thus, you should print 2.
The other pairs do not satisfy the conditions. For instance, for (1, 3), the graph G has an edge connecting vertex 1 and vertex 3; for (4, 5), adding an edge connecting vertex 4 and vertex 5 in the graph G does not result in a bipartite graph.

Sample Input 2

4 3
3 1
3 2
1 2

Sample Output 2

0

Note that the given graph may not be bipartite or connected.

Sample Input 3

9 11
4 9
9 1
8 2
8 3
9 2
8 4
6 7
4 6
7 5
4 5
7 8

Sample Output 3

9

Problem Statement

You are given an integer sequence A=(A_1,\ldots,A_N) of length N. Find the value of the following expression:

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^8
• All input values are integers.

Sample Input 1

3
1 3 2

Sample Output 1

3

A_1 \oplus A_2 = 2, A_1 \oplus A_2 \oplus A_3 = 0, and A_2 \oplus A_3 = 1, so the answer is 2 + 0 + 1 = 3.

Sample Input 2

7
2 5 6 5 2 1 7

Sample Output 2

83

Problem Statement

You are given three integer sequences of length N, namely A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N), and C=(C_1,C_2,\ldots,C_N), and an integer K.

For each of the N^3 choices of integers i,j,k (1\leq i,j,k\leq N), compute the value A_iB_j + B_jC_k + C_kA_i. Among all these values, find the K-th largest value.

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq K \leq \min(N^3,5\times 10^5)
• 1\leq A_i,B_i,C_i \leq 10^9
• All input values are integers.

Sample Input 1

2 5
1 2
3 4
5 6

Sample Output 1

31

The N^3=8 values are computed as follows:

• For (i,j,k)=(1,1,1): A_1B_1+B_1C_1+C_1A_1=1\times 3+3\times 5+5\times 1=23
• For (i,j,k)=(1,1,2): A_1B_1+B_1C_2+C_2A_1=1\times 3+3\times 6+6\times 1=27
• For (i,j,k)=(1,2,1): A_1B_2+B_2C_1+C_1A_1=1\times 4+4\times 5+5\times 1=29
• For (i,j,k)=(1,2,2): A_1B_2+B_2C_2+C_2A_1=1\times 4+4\times 6+6\times 1=34
• For (i,j,k)=(2,1,1): A_2B_1+B_1C_1+C_1A_2=2\times 3+3\times 5+5\times 2=31
• For (i,j,k)=(2,1,2): A_2B_1+B_1C_2+C_2A_2=2\times 3+3\times 6+6\times 2=36
• For (i,j,k)=(2,2,1): A_2B_2+B_2C_1+C_1A_2=2\times 4+4\times 5+5\times 2=38
• For (i,j,k)=(2,2,2): A_2B_2+B_2C_2+C_2A_2=2\times 4+4\times 6+6\times 2=44

Sorting these values in descending order, we have (44,38,36,34,31,29,27,23), so the 5th largest value is 31.

Sample Input 2

3 10
100 100 100
100 100 100
100 100 100

Sample Output 2

30000

Sample Input 3

5 54
800516877 573289179 26509423 168629803 696409999
656737335 915059758 201458890 931198638 185928366
140174496 254538849 830992027 305186313 322164559

Sample Output 3

689589940713840351