Problem Statement

We have a sequence of length N, a = (a_1, a_2, ..., a_N). Each a_i is a positive integer.

Snuke's objective is to permute the element in a so that the following condition is satisfied:

• For each 1 ≤ i ≤ N - 1, the product of a_i and a_{i + 1} is a multiple of 4.

Determine whether Snuke can achieve his objective.

Constraints

• 2 ≤ N ≤ 10^5
• a_i is an integer.
• 1 ≤ a_i ≤ 10^9

Sample Input 1

3
1 10 100

Sample Output 1

Yes

One solution is (1, 100, 10).

Sample Input 2

4
1 2 3 4

Sample Output 2

No

It is impossible to permute a so that the condition is satisfied.

Sample Input 3

3
1 4 1

Sample Output 3

Yes

The condition is already satisfied initially.

Sample Input 4

2
1 1

Sample Output 4

No

Sample Input 5

6
2 7 1 8 2 8

Sample Output 5

Yes

Problem Statement

We have a grid with H rows and W columns of squares. Snuke is painting these squares in colors 1, 2, ..., N. Here, the following conditions should be satisfied:

• For each i (1 ≤ i ≤ N), there are exactly a_i squares painted in Color i. Here, a_1 + a_2 + ... + a_N = H W.
• For each i (1 ≤ i ≤ N), the squares painted in Color i are 4-connected. That is, every square painted in Color i can be reached from every square painted in Color i by repeatedly traveling to a horizontally or vertically adjacent square painted in Color i.

Find a way to paint the squares so that the conditions are satisfied. It can be shown that a solution always exists.

Constraints

• 1 ≤ H, W ≤ 100
• 1 ≤ N ≤ H W
• a_i ≥ 1
• a_1 + a_2 + ... + a_N = H W

Sample Input 1

2 2
3
2 1 1

Sample Output 1

1 1
2 3

Below is an example of an invalid solution:

1 2
3 1

This is because the squares painted in Color 1 are not 4-connected.

Sample Input 2

3 5
5
1 2 3 4 5

Sample Output 2

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

Sample Input 3

1 1
1
1

Sample Output 3

1

Problem Statement

Let N be a positive even number.

We have a permutation of (1, 2, ..., N), p = (p_1, p_2, ..., p_N). Snuke is constructing another permutation of (1, 2, ..., N), q, following the procedure below.

First, let q be an empty sequence. Then, perform the following operation until p becomes empty:

• Select two adjacent elements in p, and call them x and y in order. Remove x and y from p (reducing the length of p by 2), and insert x and y, preserving the original order, at the beginning of q.

When p becomes empty, q will be a permutation of (1, 2, ..., N).

Find the lexicographically smallest permutation that can be obtained as q.

Constraints

• N is an even number.
• 2 ≤ N ≤ 2 × 10^5
• p is a permutation of (1, 2, ..., N).

Sample Input 1

4
3 2 4 1

Sample Output 1

3 1 2 4

The solution above is obtained as follows:

Sample Input 2

2
1 2

Sample Output 2

1 2

Sample Input 3

8
4 6 3 2 8 5 7 1

Sample Output 3

3 1 2 7 4 6 8 5

The solution above is obtained as follows:

Problem Statement

There are infinitely many cards, numbered 1, 2, 3, ... Initially, Cards x_1, x_2, ..., x_N are face up, and the others are face down.

Snuke can perform the following operation repeatedly:

• Select a prime p greater than or equal to 3. Then, select p consecutive cards and flip all of them.

Snuke's objective is to have all the cards face down. Find the minimum number of operations required to achieve the objective.

Constraints

• 1 ≤ N ≤ 100
• 1 ≤ x_1 < x_2 < ... < x_N ≤ 10^7

Sample Input 1

2
4 5

Sample Output 1

2

Below is one way to achieve the objective in two operations:

• Select p = 5 and flip Cards 1, 2, 3, 4 and 5.
• Select p = 3 and flip Cards 1, 2 and 3.

Sample Input 2

9
1 2 3 4 5 6 7 8 9

Sample Output 2

3

Below is one way to achieve the objective in three operations:

• Select p = 3 and flip Cards 1, 2 and 3.
• Select p = 3 and flip Cards 4, 5 and 6.
• Select p = 3 and flip Cards 7, 8 and 9.

Sample Input 3

2
1 10000000

Sample Output 3

4