Orange Ami Vol.2 Div 1

ami có một dãy số nguyên dương \(A\) gồm \(n\) phần tử và một số nguyên dương \(k\).

Các bạn có thể thực hiện thao tác sau không quá k lần, mỗi lần, các bạn có thể chọn một phần tử trong \(A\) và giảm giá trị của nó đi 1.

Hãy tìm cách thực hiện thao tác trên một cách tối ưu để trị tuyệt đối của tích \(A\) là nhỏ nhất. Nói cách khác, các bạn cần cực tiểu giá trị \(S\) sau:

\(S\) = |\(A_1 * A_2 * ... * A_n\)|

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) lần lượt là số phần tử của dãy \(A\) và số lần thực hiện thao tác tối đa.

• Dòng tiếp theo chứa \(n\) số nguyên dương \(A_i\) biểu thị một phần tử của dãy \(A\).

Output

• Hãy in ra giá trị \(S\) sau khi chia dư cho \(10^9+7\).

Scoring

• Trong toàn bộ dữ liệu có \(1 \leq a_i \leq 10^9\).

• \(50\)% điểm tương ứng với \(1 \leq n, m \leq 10\).

• \(50\)% điểm tương ứng với \(1 \leq n, m \leq 2*10^5\).

Example

3 3
1 2 3

0

2 1
2 2

2

ami có một dãy hoán vị \(A\) độ dài \(n\). Nhắc lại, một hoán vị độ dài \(n\) là một dãy số mà mỗi số nguyên dương từ \(1\) đến \(n\) đều xuất hiện trong dãy đúng một lần.

Các bạn có thể chọn cặp số \(i\) và \(j\) khác nhau và đổi chỗ \(A_i\) và \(A_j\). Các bạn được áp dụng thao tác trên đúng 1 lần. Mục đích là cần làm cho giá trị \(S\) sau đạt lớn nhất:

\(S\) = \(\sum A_i * (n+1)^{1 + n - i}\) \(\forall\) \(1 \leq i \leq n\).

Hãy in ra dãy số tối ưu \(A\) sau khi thực hiện thao tác trên đúng một lần. Nếu có nhiều đáp án, các bạn có thể in ra một đáp án bất kì.

Input

Dòng đầu tiên chứa hai số nguyên dương \(n\) là số phần tử của dãy \(A\).

Dòng tiếp theo chứa \(n\) số nguyên dương \(A_i\) biểu thị một phần tử của dãy \(A\).

Dữ liệu đảm bảo dãy

Output

Hãy in ra dãy \(A\) sau khi thực hiện thao tác một cách tối ưu.

Sample Input 1

3 
1 2 3

Sample Output 1

3 2 1

Sample Input 2

2
1 2

Sample Output 2

2 1

Giới hạn

• \(50\)% điểm tương ứng với \(2 \leq n\leq 10\).

• \(50\)% điểm tương ứng với \(2 \leq n \leq 5000\).

Giải thích

Ở ví dụ 1, các cách thực hiện thao tác là:

• Đổi cặp (1, 2) ta được 2 1 3, tổng \(S\) = \(2*4^2 + 1*4^1 + 3*4^0\) = 39.
• Đổi cặp (2, 3) ta được 1 3 2, tổng \(S\) = \(1*4^2 + 3*4^1 + 2*4^0\) = 30.
• Đổi cặp (1, 3) ta được 3 2 1, tổng \(S\) = \(3*4^2 + 2*4^1 + 1*4^0\) = 57.

Vậy đáp án là [3 2 1].

Ở ví dụ 2, chỉ có một cách đổi là đổi cặp (1, 2). Ta sẽ nhận được dãy [2 1].

ami có một dãy số nguyên dương \(A\) và một số nguyên dương \(k\).

Nhận thấy dãy \(A\) không mang tính nghệ thuật, ami muốn tách dãy \(A\) thành một vài dãy con liên tiếp thoả mãn điều kiện sau:

• Mỗi một phần tử \(A_i\) đều thuộc một và chỉ một dãy con.
• Các phần tử trong cùng một dãy con phải có cùng giá trị.
• Độ dài một dãy con không vượt quá \(k\).

Các bạn hãy đếm xem có bao nhiêu cách khác nhau để ami có thể chia dãy thoả mãn các điều kiện trên. Hai cách chia gọi là khác nhau nếu tồn tại hai phần tử \(i\) và \(j\) khác nhau mà chúng ở chung một nhóm trong một cách, nhưng lại khác nhóm ở cách còn lại.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) là số phần tử của dãy \(A\).

• \(n\) dòng tiếp theo, mỗi dòng chứa \(1\) số nguyên dương \(A_i\) biểu thị một phần tử của dãy \(A\) \((1 \leq a_i \leq n)\).

• Dòng cuối cùng chứa số nguyên dương \(k\) là số phần tử tối đa trong một nhóm.

Output

• Hãy in ra số cách chia khác nhau thoả mãn điều kiện trên sau khi chia dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(1 \leq k \leq n \leq 300\).

• Subtask \(2\) (\(15\%\) số điểm): \(1 \leq k \leq n \leq 5000\).

• Subtask \(3\) (\(25\%\) số điểm): \(1 \leq k \leq n \leq 2*10^5\).

Example

4 
1 
2 
3
1
1

1

4 
2
3 
3
3
2

3

ami có một ma trận 2 chiều A gồm n hàng và m cột. Các hàng và cột được đánh số từ 0. Ô nằm trên giao của hàng i và cột j được kí hiệu là ô (i , j). Mỗi ô trong ma trận được tô một màu là \(A_{i,j}\).

Từ một ô (\(x_1\) , \(y_1\)) ta có thể đi đến ô (\(x_2\) , \(y_2\)) nếu hai ô này có cùng màu và chung một cạnh. Hai ô (\(x_1\) , \(y_1\)) và (\(x_2\) , \(y_2\)) được gọi là liên thông nếu ta có thể di chuyển từ ô (\(x_1\) , \(y_1\)) đến ô (\(x_2\) , \(y_2\)) qua một vài ô trung gian thoả mãn điều kiện ở trên.

Các bạn cần trả lời một vài câu hỏi của ami. Mỗi câu hỏi là một cặp ô (\(x_1\) , \(y_1\)) và (\(x_2\) , \(y_2\)), các bạn cần xác định xem có cách nào làm 2 ô này liên thông nếu đổi màu tối đa một ô trong ma trận hay không.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) là số hàng của ma trận.

• Dòng tiếp theo chứa số nguyên dương \(m\) là số cột của ma trận.

• \(n\) dòng tiếp theo, môi dòng chứa \(m\) số nguyên dương biểu thị một màu của một ô trong ma trận.

• Tiếp theo là một số nguyên dương \(q\) là số câu hỏi.

• Dòng tiếp theo chứa số 4.

• \(q\) dòng tiếp theo, mỗi dòng chứa 4 số nguyên dương \(x_1\) , \(y_1\) , \(x_2\) , \(y_2\) biểu thị một câu hỏi.

Output

• Với mỗi câu hỏi, hãy in ra "YES" nếu hai ô đó liên thông và "NO" nếu ngược lại

Scoring

Trong tất cả các test có \(1 \leq X \leq 10^{6}\).

• Subtask \(1\) (\(60\%\) số điểm): \(1 \leq n, m, q \leq 50\).

• Subtask \(2\) (\(15\%\) số điểm): \(1 \leq n, m, q \leq 100\).

• Subtask \(3\) (\(25\%\) số điểm): \(1 \leq n, m, q \leq 500\).

Example

3
3
1 2 1
1 1 3
2 2 1
3
4
0 0 2 2
0 0 1 1
1 2 2 0

YES
YES
NO

ami có một đồ thị dạng cây gồm \(n\) nút, mỗi nút được đánh số từ 1. Nút \(i\) được tô màu \(a_i\).

ami cần các bạn tính tổng tất cả đường đi ngắn nhất giữa hai nút u và v được tô cùng một chung màu. Tổng có thể được biểu diễn như sau:

\(\sum dist(u , v)\) \(\forall\) \(u \leq v\) và \(a_u = a_v\).

Trong đó, \(dist(u , v)\) là độ dài đường đi ngắn nhất giữa hay nút \(u\) và \(v\). Độ dài một đường đi từ u đến v được tính bằng tổng số cạnh nằm trên đường đi đó.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) là số đỉnh của cây.

• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_i\) biểu thị một màu của đỉnh \(i\).

• \(n\) dòng tiếp theo, môi dòng chứa \(2\) số nguyên dương \(u\) và \(v\) biểu thị một cạnh nối giữa hai đỉnh \(u\) và \(v\).

Output

• Hãy in ra tổng cần tìm

Scoring

• Subtask \(1\) (\(18\%\) số điểm): \(1 \leq n \leq 10\) và \(1 \leq a_i \leq 3*10^5\).

• Subtask \(2\) (\(18\%\) số điểm): \(1 \leq n \leq 1000\) và \(1 \leq a_i \leq 3*10^5\).

• Subtask \(3\) (\(18\%\) số điểm): \(1 \leq n \leq 3*10^5\) và \(1 \leq a_i \leq 10\).

• Subtask \(4\) (\(46\%\) số điểm): \(1 \leq n \leq 3*10^5\) và \(1 \leq a_i \leq 3*10^5\).

Example

4
1 3 1 3
1 2
2 3
2 4

3

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

30