2017 Fall Waterloo ACM Local Contest
A. Art
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Vera has five sticks of distinct lengths l1, l2, l3, l4, l5. Vera may choose any three of the five sticks to form the sides of a triangle. How many different triangles can Vera make? Each triangle must have positive area and sticks cannot be bent or cut.

Input

Line 1 contains integers l1, l2, l3, l4, l5 (1 ≤ li ≤ 1000).

Output

Print one line with one integer, the number of ways to form a triangle.

Examples
Input
1 2 3 4 5
Output
3
Input
1 2 4 8 16
Output
0
Note

For the first example, the 3 ways to form a triangle are choosing sticks 2, 3, 4 or 2, 4, 5 or 3, 4, 5.

B. Biology
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Vera has A × B cards. Each card has a rank, an integer between 0 and A - 1, and a suit, an integer between 0 and B - 1. All cards are distinct. A set of five different cards is known as a hand. Each hand is in exactly one of nine categories numbered from 1 to 9. If a hand satisfies the conditions for membership in multiple categories, it is considered to be in the lowest-numbered such category. The rules for each category are:

  1. Straight flush: is a Straight and a Flush.
  2. Four of a kind: four of the cards have the same rank.
  3. Full house: three of the cards have the same rank and the remaining two have the same rank.
  4. Flush: all five cards have the same suit.
  5. Straight: the ranks of the cards in increasing order are x, x + 1, x + 2, x + 3, x + 4 for some integer x.
  6. Three of a kind: three of the cards have the same rank.
  7. Two pair: two cards have the same rank and two other cards have the same rank.
  8. One pair: two cards have the same rank.
  9. High card: if a hand does not satisfy any other category.

Currently, Vera has two cards with ranks a1, a2 and suits b1, b2. Of the remaining cards, Vera will choose three more cards and form a hand with her two current cards. Compute the number of different hands formed in this way that belong in each category.

Input

Line 1 contains integers A and B (5 ≤ A ≤ 25, 1 ≤ B ≤ 4).

Line 2 contains integers a1, b1, a2, b2 (0 ≤ a1, a2 ≤ A - 1, 0 ≤ b1, b2 ≤ B - 1, (a1, b1) ≠ (a2, b2)).

Output

Print one line with nine integers, the number of different of hands that belong in each category in increasing order of categories (from Straight flush to High card).

Examples
Input
5 2
1 0 3 1
Output
0 0 0 0 8 0 12 36 0
Input
13 4
0 0 1 0
Output
1 2 18 164 63 308 792 7920 10332
Note

Let (a, b) denote a card with rank a and suit b.

For the first example, Vera currently has cards (1, 0) and (3, 1). If she chooses additional cards (3, 0), (4, 0), (4, 1), her hand will be a Two pair as there are two cards with rank 3 and two other cards with rank 4. Note that this hand also satisfies being a One pair, but Two pair is the lower-numbered category.

C. Computer Science
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Vera has N integers a1, ..., aN. A margin is a non-negative integer L such that it is possible to choose N integers x1, ..., xN such that for all i, 1 ≤ i ≤ N, the interval [xi, xi + L] contains at least K of Vera's integers and also contains ai.

Compute the minimum possible margin.

Input

Line 1 contains integers N and K (1 ≤ K ≤ N ≤ 2 × 105).

Line 2 contains N integers, a1, ..., aN ( - 109 ≤ ai ≤ 109).

Output

Print one line with one integer, the minimum possible margin.

Example
Input
5 3
1 -2 10 5 4
Output
6
Note

For the first example, one possible solution is to choose x1 =  - 1, x2 =  - 2, x3 = 4, x4 = 0, x5 = 0, which is illustrated below.

D. Drama
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Vera has a grid with H rows and N columns. Rows are numbered 1 to H and columns are numbered 1 to N. Let the cell in the r-th row and c-th column be (r, c). Cells are coloured white or black. A colouring is a pyramid if:

  • Exactly N cells are black.
  • (1, 1) is black.
  • If (r, a) and (r, b) are black, then (r, k) is black for a < k < b.
  • If (r, c) is black, then (r - 1, c), if it exists, is black.
  • If (r, c) is black and there is no k < c such that (r, k) is black, then (r + 1, c), if it exists, is white.

Two pyramids are different if there is a cell that is white in one pyramid and black in the other. Compute the number of different pyramids modulo 109 + 7.

Input

Line 1 contains integers H and N (1 ≤ H, N ≤ 105).

Output

Print one line with one integer, the number of different pyramids modulo 109 + 7.

Examples
Input
2 6
Output
7
Input
3 20
Output
487
Note

For the first example, the seven pyramids are: 


###### ####.. ####.. #####. #####. #####. #####.
...... .##... ..##.. .#.... ..#... ...#.. ....#.

E. English
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Vera has N rectangles. The i-th rectangle has corners (ai, bi) and (ci, di). Let U be the union of the N rectangles. The intersection of U and the line y = s - x is composed of disjoint line segments (maybe degenerate ones). Let f(s) be the sum of the lengths of these line segments or be zero if the intersection is empty.

Given integers L and R, let . It can be seen that for some integer V. Compute the value of V.

Input

Line 1 contains integers N, L, R (1 ≤ N ≤ 103,  - 2 × 108 ≤ L < R ≤ 2 × 108).

N lines follow. The i-th line contains integers ai, bi, ci, di ( - 108 ≤ ai < ci ≤ 108,  - 108 ≤ bi < di ≤ 108).

Output

Print one line with one integer, the value of V.

Example
Input
3 -1 3
-2 -1 0 2
-1 0 1 1
1 -2 2 -1
Output
7
Note

The below figure illustrates the first example when s = 0. f(0) is the sum of the lengths of the two thick blue line segments. Note that .