Có \(n\) drone được đánh số liên tiếp từ \(L\) đến \(L + n - 1\).
Danh sách hiện tại chỉ còn \(n - 1\) số hiệu do một drone bị mất.
Hãy xác định số hiệu của drone bị thiếu.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, L\) (\(1 \le n \le 10^5\), \(1 \le L \le 10^9\)).
• Dòng thứ hai chứa \(n - 1\) số nguyên, là danh sách số hiệu của các drone còn lại.

Output

• In ra một số nguyên duy nhất, là số hiệu của drone bị thiếu.

Examples

5 1
5 1 3 2

4

5 100
104 102 103 100

101

Scoring

• Subtask 1 (70% số điểm): \(n \le 10\), \(L \le 10\).
• Subtask 2 (30% số điểm): Không có ràng buộc gì thêm. (trùng global constraint)

Nam có \(n\) drone được, mỗi drone thuộc một trong hai loại: loại \(1\) và loại \(2\). Sau một buổi trình diễn, Nam tập hợp lại và xếp thành một dãy \(s_1, s_2, \ldots, s_n\), trong đó \(s_i = 1\) hoặc \(s_i = 2\) cho biết drone thứ \(i\) (\(1 \le i \le n\)) thuộc loại 1 hoặc loại 2. Nam muốn sắp xếp lại dãy drone để loại 1 xếp trước loại 2 chỉ bằng các thao tác đổi chỗ hai drone cho nhau. Cụ thể, mỗi lượt Nam có thể tráo đổi drone ở vị trí \(i\) (\(1 \le i \le n\)) với drone ở vị trí \(j\) (\(1 \le j \le n\)) cho nhau.

Yêu cầu: Hãy tính số lượt đổi chỗ hai drone ít nhất cần thực hiện để tất cả các drone loại 1 xếp trước loại 2.

Đầu vào

• Dòng đầu tiên chứa số nguyên \( n \) \((1 \le n \le 10^5\)).
• Dòng thứ hai chứa \( n \) số nguyên \( s_1, s_2, \dots, s_n \) \((1 \le s_i \le 2)\).

Đầu ra

• Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là số lần đổi chỗ hai drone ít nhất cần thực hiện.

Ví dụ

2
1 2

0

5
2 2 1 1 2

2

Cho ba số nguyên dương \(A, B, K\) (\(1 \leq A, B \leq 10^9\), \(1 \leq K \leq 15\)).

Yêu cầu: Hãy tìm số nguyên dương \(C\) nhỏ nhất sao cho tích của ba số \(𝐴, B, C\) có ít nhất \(K\) chữ số \(0\) tận cùng.

Input

• Nhập vào ba số nguyên dương lần lượt theo thứ tự là \(A, B\) và \(K\). Mỗi số viết trên một dòng.

Output

• Đưa ra một số duy nhất là số nguyên dương \(C\) thỏa mãn yêu cầu đề bài.

Scoring

• Nếu chương trình chạy đúng những trường hợp \(1 \leq A, B \leq 10^3, 1 \leq K \leq 9\), thí sinh sẽ được \(40\) điểm;
• Nếu chương trình chạy đúng những trường hợp \(1 \leq A, B \leq 10^9, 1 \leq K \leq 15\) thí sinh sẽ được \(100\) điểm

Example

15
12
2

5

Đếm cặp \((i, j)\) thỏa mãn tích là số chính phương

Cho một số nguyên dương \(N\). Đếm các cặp nguyên dương \((i, j)\) có giá trị không vượt quá \(N\) thỏa mãn điều kiện \(i \times j\) là một số chính phương.

Input

Gồm một số nguyên dương \(N\).

Output

In ra kết quả của bài toán.

Sample Test

4

6

Giải thích

Có 6 cặp thỏa mãn là: \((1,1); (1,4); (2,2); (3,3); (4,1); (4,4)\).

Ràng buộc

• Có 60% số test tương ứng với 60% số điểm của bài thỏa mãn: \(1 \leq N \leq 5000\);
• Có 40% số test khác tương ứng với 40% số điểm của bài thỏa mãn: \(N \leq 10^{5}\).

Trong một trò chơi, có \(N\) người chơi xếp thành một vòng tròn và được đánh số từ \(1\) đến \(N\) theo chiều kim đồng hồ. Trước khi trò chơi bắt đầu, sẽ có \(M\) lượt phát đồng xu cho người chơi với nguyên tắc như sau:

• Mỗi lượt, chọn ngẫu nhiên hai số nguyên dương \(L\) và \(R\) \((L \le R)\), phát một đồng xu cho tất cả những người chơi từ số \(L\) đến số \(R\) theo chiều kim đồng hồ.

Yêu cầu: Cho trước \(N\), \(M\) và các cặp \(L\), \(R\). Tìm:

• Số đồng xu lớn nhất mà một người chơi được phát.
• Số người chơi nhận được số đồng xu lớn nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(M\) \((1 \le M \le 10^5)\).
• \(M\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(L\) và \(R\) \((1 \le L, R \le N)\).

Output

• Gồm hai số nguyên:
• Số đồng xu lớn nhất mà một người chơi được phát.
• Số người chơi đạt được số đồng xu đó.

Subtasks

• 60% số test: \(N, M \le 10^3\)
• 20% số test: \(N \le 10^5\)
• 20% số test: \(N \le 10^9\), \(M \le 10^5\)

Sample Test

5 2
1 5
4 2

2 4

Giải thích

• Số đồng xu của mỗi người theo thứ tự:
• Ban đầu: 0 0 0 0 0
• Lượt 1 (1 → 5): 1 1 1 1 1
• Lượt 2 (4 → 2): 2 2 1 2 2
  => Người có nhiều đồng nhất: 2 đồng xu. Số người có 2 đồng xu: 4.

Trước mặt cnn008 hiện tại có \(N\) ngọn núi, ngọn núi thứ \(i\) có độ cao là \(h_i\). cnn008 định nghĩa một dãy núi là một dãy các ngọn núi liên tiếp, mà chiều cao của các ngọn núi tăng dần cho đến đỉnh, sau đó giảm dần. Ví dụ dãy \([1, 2, 3, 2, 1]\), \([1, 2, 3]\), \([5, 3, 2]\) là các dãy núi, còn \([1, 2, 4, 2, 3]\), \([4, 4, 6, 3, 4]\) không phải là dãy núi. Nói cách khác, một dãy các ngọn núi \(h_1, h_2, \dots, h_k\) là một dãy núi khi tồn tại một chỉ số \(1 \le x \le k\) sao cho \(h_1 \le h_2 \le \dots \le h_x \ge h_{x + 1} \ge \dots h_k\).

cnn008 đang tận hưởng view triệu đô của mình, cnn008 muốn nhờ bạn trả lời \(Q\) câu hỏi. Câu hỏi thứ \(i\) gồm hai số \(l_i, r_i\), và bạn phải kiểm tra xem các ngọn núi từ \(l_i\) đến \(r_i\) có phải là một dãy núi hay không?

Input

• Dòng đầu gồm hai số nguyên dương \(N\), \(Q\).
• Dòng thứ hai gồm một dãy \(N\) số nguyên dương \(h_1, h_2, \dots, h_N\) \((1 \le h_i \le 10^9)\).
• \(Q\) dòng sau, mỗi dòng gồm hai số nguyên dương \(l_i, r_i\) \((1 \le l_i \le r_i \le N)\) là câu hỏi thứ \(i\).

Output

• In ra \(Q\) dòng, dòng thứ \(i\) là Yes nếu các ngọn núi từ \(l_i\) đến \(r_i\) là một dãy núi, ngược lại in No.

Sample Input

6 5
4 1 2 1 4 5 
1 1
2 5
2 6
2 4 
1 4

Sample Output

Yes
No
No
Yes
No

Notes

• Trong câu hỏi đầu tiên, dãy \([4]\) là một đồi núi.
• Trong câu hỏi thứ hai, dãy \([1, 2, 1, 4]\) không phải là một đồi núi.
• Trong câu hỏi thứ tư, dãy \([1, 2, 1]\) là một đồi núi.

Scoring

• Subtask \(1\) \((40\%)\): \(N, Q \le 2000\).
• Subtask \(2\) \((60\%)\): \(N, Q \le 10^5\).

Cho dãy gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) chỉ gồm các số \(1\), \(2\) và \(3\). Đếm số cách xoá một vài phần tử của dãy (có thể không xoá) để nhận được một dãy thoả mãn hai yêu cầu sau:

1. Dãy còn ít nhất \(3\) phần tử
2. Phần tử đầu tiên của dãy có giá trị \(1\), tiếp theo là một số phần tử có giá trị \(2\) (ít nhất một số \(2\)), kết thúc bằng đúng một phần tử có giá trị \(3\).

Ví dụ: các dãy \(\{1, 2, 2, 3\}\) và dãy \(\{1, 2, 3\}\) thoả mãn yêu cầu, các dãy \(\{1, 2, 3, 3\}\) và dãy \(\{1, 1, 2, 3\}\) không thoả mãn yêu cầu.

Vì số cách xoá có thể rất lớn, hãy in ra số cách xoá chia lấy dư cho \(10^9+7\).

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 10^6\)) là số lượng phần tử của dãy.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 3\)) mô tả các phần tử của dãy.

Output

Gồm một dòng duy nhất chứa một số nguyên là số cách xoá thoả mãn yêu cầu đề bài, chia lấy dư cho \(10^9+7\).

Sample Test

Input:

8
1 2 1 2 3 1 2 3

Output

15

Một lớp học có \(N\) học sinh, học sinh thứ \(i\) (\(1 \leq i \leq N\)) có mã học sinh là số nguyên dương \(a_i\). Hai học sinh có mã học sinh khác nhau. Cuối năm học, thầy giáo chủ nhiệm phát kẹo thưởng cho cả lớp. Là một giáo viên dạy môn Tin học nên thầy sẽ phát kẹo theo quy tắc sau:

• Tất cả \(N\) học sinh đứng thành một hàng, học sinh thứ \(i\) đứng ở vị trí \(i\) tính từ đầu hàng;
• Thầy sẽ phát kẹo \(Q\) lượt, mỗi lượt:
• Thầy sẽ chọn bốn số nguyên dương \(l, r, x, v\);
• Thầy sẽ đi từ vị trí \(l\) đến vị trí \(r\) để phát kẹo, khi tới vị trí \(i\) (\(l \leq i \leq r\)), nếu mã học sinh \(a_i\) chia hết cho \(x\) thì học sinh đó nhận được \(v\) viên kẹo.

Sau \(Q\) lượt phát kẹo, thầy muốn biết mỗi bạn học sinh có số kẹo là bao nhiêu.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(Q\) (\(1 \leq N, Q \leq 2 \times 10^{5}\));
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_i\) (\(1 \leq a_i \leq 5 \times 10^{5}\));
• \(Q\) dòng tiếp theo, mỗi dòng gồm bốn số nguyên dương \(l, r, x, v\) (\(1 \leq l \leq r \leq N; 1 \leq x \leq 5 \times 10^{5}; v \leq 10^{9}\)).

Kết quả ra

• Một dòng chứa \(N\) số nguyên dương lần lượt là số kẹo của học sinh.

Ví dụ

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

0 1 5 3 7 2

Ràng buộc

• Có 20% số test ứng với 20% số điểm có: \(N, Q \leq 10^{3}\);
• 20% số test ứng với 20% số điểm có: \(x = 1\) với lần phát kẹo;
• 20% số test ứng với 20% số điểm có: \(x \leq 2\) với lần phát kẹo;
• 20% số test ứng với 20% số điểm có: \(l = 1\), \(r = N\) với mọi lần phát kẹo;
• 20% số test còn lại không có ràng buộc gì thêm.

Cho một hình chữ nhật gồm \( N \) dòng và \( M \) cột. Các dòng được đánh số từ 1 đến \( N \) , từ trên xuống dưới. Các cột được đánh số từ 1 đến \( M \) , từ trái sang phải. Ô ở dòng thứ \( i \) và cột thứ \( j \) được gọi là ô (\( i, j \)) và có diện tích là 1 đơn vị. Có một số ô đã được điền sẵn kí tự \( 'X' \).

Yêu cầu: tìm hình chữ nhật con có diện tích lớn nhất chỉ chứa duy nhất một kí tự \( 'X' \).

Input

• Dòng đầu tiên gồm ba số nguyên dương \( N, M, K \)(\( N, M ≤ 10^4, K ≤ 10^3 \)) mô tả kích thước của hình chữ nhật và số lượng kí tự \( ′X′ \) có trong hình chữ nhật;
• \(K\) dòng sau, mỗi dòng gồm hai số nguyên dương \( d \) và \( c \) là chỉ số dòng và cột của ô điền kí tự \( ′X′ \) (\( d ≤ N; c ≤ M\)).

Output

• Ghi ra diện tích của hình chữ nhật lớn nhất thoả mãn yêu cầu đề bài..

Scoring

• Có 50% số test tương ứng với 50% số điểm thoả mãn: \( N, M ≤ 50 \) ;
• 30% số test khác tương ứng với 30% số điểm thoả mãn: \( N, M ≤ 500 \);
• 20% số test còn lại tương ứng với 20% số điểm không có ràng buộc gì thêm.

Example

4 5 4
2 3
2 5
3 1
4 4

9