Problem Statement

Niwango-kun is an employee of Dwango Co., Ltd.
One day, he is asked to generate a thumbnail from a video a user submitted.
To generate a thumbnail, he needs to select a frame of the video according to the following procedure:

• Get an integer N and N integers a_0, a_1, ..., a_{N-1} as inputs. N denotes the number of the frames of the video, and each a_i denotes the representation of the i-th frame of the video.
• Select t-th frame whose representation a_t is nearest to the average of all frame representations.
• If there are multiple such frames, select the frame with the smallest index.

Find the index t of the frame he should select to generate a thumbnail.

Constraints

• 1 \leq N \leq 100
• 1 \leq a_i \leq 100
• All numbers given in input are integers

Sample Input 1

3
1 2 3

Sample Output 1

1

Since the average of frame representations is 2, Niwango-kun needs to select the index 1, whose representation is 2, that is, the nearest value to the average.

Sample Input 2

4
2 5 2 5

Sample Output 2

0

The average of frame representations is 3.5.
In this case, every frame has the same distance from its representation to the average.
Therefore, Niwango-kun should select index 0, the smallest index among them.

Problem Statement

One day, Niwango-kun, an employee of Dwango Co., Ltd., found an integer sequence (a_1, ..., a_N) of length N. He is interested in properties of the sequence a.

For a nonempty contiguous subsequence a_l, ..., a_r (1 \leq l \leq r \leq N) of the sequence a, its beauty is defined as a_l + ... + a_r. Niwango-kun wants to know the maximum possible value of the bitwise AND of the beauties of K nonempty contiguous subsequences among all N(N+1)/2 nonempty contiguous subsequences. (Subsequences may share elements.)

Find the maximum possible value for him.

Constraints

• 2 \leq N \leq 1000
• 1 \leq a_i \leq 10^9
• 1 \leq K \leq N(N+1)/2
• All numbers given in input are integers

Sample Input 1

4 2
2 5 2 5

Sample Output 1

12

There are 10 nonempty contiguous subsequences of a. Let us enumerate them:

• contiguous subsequences starting from the first element: \{2\}, \{2, 5\}, \{2, 5, 2\}, \{2, 5, 2, 5\}
• contiguous subsequences starting from the second element: \{5\}, \{5, 2\}, \{5, 2, 5\}
• contiguous subsequences starting from the third element: \{2\}, \{2, 5\}
• contiguous subsequences starting from the fourth element: \{5\}

(Note that even if the elements of subsequences are equal, subsequences that have different starting indices are considered to be different.)

The maximum possible bitwise AND of the beauties of two different contiguous subsequences is 12. This can be achieved by choosing \{5, 2, 5\} (with beauty 12) and \{2, 5, 2, 5\} (with beauty 14).

Sample Input 2

8 4
9 1 8 2 7 5 6 4

Sample Output 2

32

Problem Statement

In Dwango Co., Ltd., there is a content distribution system named 'Dwango Media Cluster', and it is called 'DMC' for short.
The name 'DMC' sounds cool for Niwango-kun, so he starts to define DMC-ness of a string.

Given a string S of length N and an integer k (k \geq 3), he defines the k-DMC number of S as the number of triples (a, b, c) of integers that satisfy the following conditions:

• 0 \leq a < b < c \leq N - 1
• S[a] = D
• S[b] = M
• S[c] = C
• c-a < k

Here S[a] is the a-th character of the string S. Indexing is zero-based, that is, 0 \leq a \leq N - 1 holds.

For a string S and Q integers k_0, k_1, ..., k_{Q-1}, calculate the k_i-DMC number of S for each i (0 \leq i \leq Q-1).

Constraints

• 3 \leq N \leq 10^6
• S consists of uppercase English letters
• 1 \leq Q \leq 75
• 3 \leq k_i \leq N
• All numbers given in input are integers

Sample Input 1

18
DWANGOMEDIACLUSTER
1
18

Sample Output 1

1

(a,b,c) = (0, 6, 11) satisfies the conditions.
Strangely, Dwango Media Cluster does not have so much DMC-ness by his definition.

Sample Input 2

18
DDDDDDMMMMMCCCCCCC
1
18

Sample Output 2

210

The number of triples can be calculated as 6\times 5\times 7.

Sample Input 3

54
DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED
3
20 30 40

Sample Output 3

0
1
2

(a, b, c) = (0, 23, 36), (8, 23, 36) satisfy the conditions except the last one, namely, c-a < k_i.
By the way, DWANGO is an acronym for "Dial-up Wide Area Network Gaming Operation".

Sample Output 4

30
DMCDMCDMCDMCDMCDMCDMCDMCDMCDMC
4
5 10 15 20

Sample Output 4

10
52
110
140

Problem Statement

Niwango-kun, an employee of Dwango Co., Ltd., likes Niconico TV-chan, so he collected a lot of soft toys of her and spread them on the floor.

Niwango-kun has N black rare soft toys of Niconico TV-chan and they are spread together with ordinary ones. He wanted these black rare soft toys to be close together, so he decided to rearrange them.

In an infinitely large two-dimensional plane, every lattice point has a soft toy on it. The coordinates (x_i,y_i) of N black rare soft toys are given. All soft toys are considered to be points (without a length, area, or volume).

He may perform the following operation arbitrarily many times:

• Put an axis-aligned square with side length D, rotate the square by 90 degrees with four soft toys on the four corners of the square. More specifically, if the left bottom corner's coordinate is (x, y), rotate four points (x,y) \rightarrow (x+D,y) \rightarrow (x+D,y+D) \rightarrow (x,y+D) \rightarrow (x,y) in this order. Each of the four corners of the square must be on a lattice point.

Let's define the scatteredness of an arrangement by the minimum side length of an axis-aligned square enclosing all black rare soft toys. Black rare soft toys on the edges or the vertices of a square are considered to be enclosed by the square.

Find the minimum scatteredness after he performs arbitrarily many operations.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq D \leq 1000
• 0 \leq x_i, y_i \leq 10^9
• Given coordinates are pairwise distinct
• All numbers given in input are integers

Partial Scores

• 500 points will be awarded for passing the test set satisfying 1 \leq D \leq 30.

Sample Input 1

3 1
0 0
1 0
2 0

Sample Output 1

1

Sample Input 2

19 2
1 3
2 3
0 1
1 1
2 1
3 1
4 4
5 4
6 4
7 4
8 4
8 3
8 2
8 1
8 0
7 0
6 0
5 0
4 0

Sample Output 2

4

Sample Input 3

8 3
0 0
0 3
3 0
3 3
2 2
2 5
5 2
5 5

Sample Output 3

4

Problem Statement

Niwango-kun has \(N\) chickens as his pets. The chickens are identified by numbers \(1\) to \(N\), and the size of the \(i\)-th chicken is a positive integer \(a_i\).

\(N\) chickens decided to take each other's hand (wing) and form some cycles. The way to make cycles is represented by a permutation \(p\) of \(1, \ldots , N\). Chicken \(i\) takes chicken \(p_i\)'s left hand by its right hand. Chickens may take their own hand.

Let us define the cycle containing chicken \(i\) as the set consisting of chickens \(p_i, p_{p_i}, \ldots, p_{\ddots_i} = i\). It can be proven that after each chicken takes some chicken's hand, the \(N\) chickens can be decomposed into cycles.

The beauty \(f(p)\) of a way of forming cycles is defined as the product of the size of the smallest chicken in each cycle. Let \(b_i \ (1 \leq i \leq N)\) be the sum of \(f(p)\) among all possible permutations \(p\) for which \(i\) cycles are formed in the procedure above.

Find the greatest common divisor of \(b_1, b_2, \ldots, b_N\) and print it \({\rm mod} \ 998244353\).

Constraints

• \(1 \leq N \leq 10^5\)
• \(1 \leq a_i \leq 10^9\)
• All numbers given in input are integers

Sample Input 1

2
4 3

Sample Output 1

3

In this case, \(N = 2, a = [ 4, 3 ]\).

For the permutation \(p = [ 1, 2 ]\), a cycle of an only chicken \(1\) and a cycle of an only chicken \(2\) are made, thus \(f([1, 2]) = a_1 \times a_2 = 12\).

For the permutation \(p = [ 2, 1 ]\), a cycle of two chickens \(1\) and \(2\) is made, and the size of the smallest chicken is \(a_2 = 3\), thus \(f([2, 1]) = a_2 = 3\).

Now we know \(b_1 = f([2, 1]) = 3, b_2 = f([1, 2]) = 12\), and the greatest common divisor of \(b_1\) and \(b_2\) is \(3\).

Sample Input 2

4
2 5 2 5

Sample Output 2

2

There are always \(N!\) permutations because chickens of the same size can be distinguished from each other.

The following picture illustrates the cycles formed and their beauties when \(p = (2, 1, 4, 3)\) and \(p = (3, 4, 1, 2)\), respectively.