Matryoshka là một loại búp bê rất nổi tiếng của Nga. Với việc có ~1~ con búp bê nằm trong ~1~ con búp bê khác, và lại có ~1~ con búp bê khác nữa nằm trong con búp bê, ... LamTer hôm nay vừa được bố mẹ mua cho ~n~ con búp bê, ~n~ con búp bê này được xếp thành ~1~ đường thẳng, con thứ ~i~ có kích thước là ~a_i~.

LamTer quyết định sẽ chồng một số con búp bê vào nhau sao cho số lượng búp bê được chồng trong ~1~ con nào đó là lớn nhất. Biết rằng con búp bê thứ ~i~ có thể chồng vào được con búp bê thứ ~j~ nếu như ~i < j~ và ~a_i < a_j~.

Hãy giúp LamTer tìm số lượng búp bê chồng vào nhau lớn nhất nhé.

Input

Gồm ~2~ dòng:

• Dòng đầu tiên chứa số nguyên dương ~n~ là số búp bê.
• Dòng thứ hai chứa ~n~ số nguyên dương thể hiện dãy ~a~.

Output

Gồm ~1~ số duy nhất là đáp án của bài toán.

Constraint

• ~n \leq 1000~
• ~a_i \leq 10^9~

Subtask

• Subtask 1 (25%): ~n \leq 20~.
• Subtask 2 (25%): ~a_i \leq 3~.
• Subtask 3 (50%): không có ràng buộc gì thêm.

Sample Input

5
1 4 3 2 5

Sample Output

3

Note

• Chọn dãy búp bê lồng nhau gồm các búp bê có kích thước ~1, 3~ và ~5~.

Summoner’s Rift là một địa điểm có kết cấu rất kỳ lạ. Được biết địa điểm này có kết cấu là một bảng ~n~ hàng và ~m~ cột, các hàng được đánh số từ ~1~ tới ~n~, các cột được đánh dấu từ ~1~ tới ~m~. Được biết ở đây có một số ô là ô cấm, có nghĩa là ô này không được đi vào.

Có một con Cua kỳ cục đang đứng ở ô ~(1, 1)~, nó đang muốn đi tới ô ~(n, m)~. Nếu Cua kỳ cục đang đứng ở ô ~(u, v)~ thì nó có thể di chuyển tới ô ~(u + 1, v)~ hoặc ~(u, v + 1)~, và nó phải đảm bảo tại mọi lúc thì ô nó di chuyển tới không phải là ô cấm và không nằm ngoài Summoner’s Rift.

Mặc dù đã biết rằng mọi con đường đều dẫn tới Summoner’s Rift nhưng mà chú Cua kỳ cục của chúng ta vẫn muốn biết có bao nhiêu cách để đi từ ô ~(1, 1)~ đến ô ~(n, m)~.

Biết rằng hai cách đi ~S_1, S_2, S_3, S_4,..., S_x~, ~T_1, T_2, T_3, T_4, ..., T_y~ được gọi là khác nhau nếu:

• ~x \neq y~.
• ~\exists i, 1 \leq i \leq \max(x, y), S_i \neq T_i~.

Các bạn hãy giúp Cua kỳ cục nhá.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ lần lượt là số hàng và cột của bảng.
• ~n~ dòng tiếp theo mỗi dòng chứa một chuỗi gồm ~m~ ký tự. Gọi ký tự thứ ~j~ ở hàng ~i~ là ~a_{i, j}~. ~a_{i, j}~ có giá trị là ~1~ thì có nghĩa ô này là ô cấm, và ngược lại.

Output

• Gồm một dòng duy nhất là số cách để Cua kỳ cục đi đến ô ~(n, m)~.
• Và vì con Cua này rất kỳ cục nên nó muốn bạn đưa ra phần dư của kết quả khi chia cho ~10^9 + 22071997~.

Constraint

• ~2 \leq n, m \leq 10^6~.
• ~n \times m \leq 10^6~.
• Dữ liệu đảm bảo ô ~(1, 1)~ và ô ~(n, m)~ không phải ô cấm.

Subtask

• Subtask 1 (25%): ~n, m \leq 4~.
• Subtask 2 (25%): ~n, m \leq 10^3~.
• Subtask 3 (50%): không có giới hạn gì thêm.

Sample Input

2 2
00
00

Sample Output

2

Với các bé ngoài việc học tập thì chúng cũng rất cần được thoả mãn nhu cầu vui chơi, giải trí. Trò “Chơi bi” vừa giúp bé có những giây phút thư giãn bên bạn bè vừa rèn luyện khả năng khéo léo khi phải cố gắng để bắn trúng những mục tiêu khác nhau.

Chơi bi hứa hẹn sẽ giúp các bé gắn kết hơn với thiên nhiên, cây cối, bớt ham mê những trò chơi điện tử vô bổ (trừ LOL). Thế giới của các bé sẽ rộng mở hơn, cùng bạn bè tạo nên những kỷ niệm giản dị nhưng thật quý báu, làm giàu thêm tình cảm, trí tuệ.

Nguồn: https://specialkid.vn/

Một hôm, đang trên đường ra sân để học thể dục, Phọm thấy rất nhiều bi vương vãi trên sân, là một “nhà sưu tầm bi”, cậu không thể bỏ lỡ cơ hội làm giàu hiếm có này. Tuy nhiên, cũng sắp trễ giờ học rồi nên cậu không thể nhặt hết bi mà chỉ nhặt bi từ phía cậu đang chạy về phía sân học thể dục.

Bãi bi có dạng một hình vuông kích thước ~n * n~, Phọm xuất phát tại ô ~(1, 1)~ và kết thúc tại ô ~(n, n)~ cũng là vị trí cuối cùng mà cậu sẽ nhặt trước khi đến sân thể dục đúng giờ. Mỗi lần di chuyển từ ô ~(x, y)~ cậu chỉ có thể đi tới ô ~(x + 1, y)~ hoặc ~(x, y + 1)~ để nhặt bi. Do Phọm không còn thời gian để suy nghĩ nên bạn hãy giúp cậu nhóc tìm đường đi sao cho số bi cậu kiếm được là lớn nhất.

Input

Dòng đầu tiên chứa một số nguyên ~n~ (~1 \le n \le 5000~).

~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên, số nguyên thứ ~j~ là ~a_{ij}~ (~0 \le a_{ij} \le 10000~) thể hiện số viên bi ở trên ô ~(i, j)~.

Output

Gồm một số nguyên duy nhất là số bi tối đa Phọm có thể lụm được.

Sample Input

4
3 3 3 4
2 3 2 2
3 4 5 6
2 3 8 8

Sample Output

34

Subtasks

Subtask 1(40%): ~n \le 15~.

Subtask 2(60%): Không có ràng buộc gì thêm.

Sau trận thua ~0-1~ muối mặt trước ĐTQG Indonesia trong khuôn khổ ASIAN CUP 2023. HLV Philippe Troussier đã quyết định sẽ gặp mặt riêng với các cầu thủ nhầm nói chuyện khích lệ động viên tinh thần. Được biết HLV sẽ nói chuyện với một cầu thủ cùng lúc.

Biết rằng ĐTQG Việt Nam có ~n~ cầu thủ, để nói chuyện với cầu thủ thứ ~i~ thì HLV sẽ cần dành ra khoảng thời gian ~[l_i, r_i)~ và lượng hào khí tăng thêm sẽ là ~c_i~ (lưu ý rằng ~c_i~ có thể âm vì có một vài cầu thủ hướng nội).

Bạn hãy giúp HLV Philippe Troussier tìm cách xếp lịch nói chuyện để hào khí của đội tuyển đạt cao nhất nhé.

Input

Dòng đầu tiên chứa một số nguyên dương ~n~ là số cầu thủ của ĐTQG Việt Nam.

~n~ dòng tiếp theo, mỗi dòng chứa ba số là ~l_i, r_i, c_i~ tương ứng.

Output

Đưa ra một số duy nhất là lượng hào khí tăng lên tối đa của đội tuyển.

Constraint

• ~n \leq 5000~.
• ~1 \leq l_i < r_i \leq 10^9~.
• ~|c_i| \leq 10^5~.

Subtask

• Subtask 1 (25%): ~n \leq 20~.
• Subtask 2 (75%): không có giới hạn gì thêm.

Sample Input

3
1 3 5
1 2 1
2 3 5

Sample Output

6

Notes

HLV sẽ họp bàn với cầu thủ thứ hai và sau đó cầu thủ thứ ba, lượng hào khí tăng thêm là ~1 + 5 = 6~.

Bạn được cho một dãy ~a~ gồm ~n~ phần tử và ~q~ truy vấn. Mỗi truy vấn gồm một số nguyên ~k~, hãy đếm số dãy con tăng của dãy ~a~ có độ dài đúng bằng ~k~.

Dãy con tăng độ dài k của dãy ~a~ là một dãy con của ~a~ thỏa mãn ~a_{i_1} < a_{i_2} < a_{i_3} < ... < a_{i_k}~ với ~i_1 < i_2 < i_3 < ... < i_k~.

Input

Dòng đàu tiên chứa 2 số nguyên ~n~ và ~q~ (~n, q \le 500~).

Dòng thứ 2 chứa ~n~ số tự nhiên, số thứ ~i~ là ~a_i~ (~a_i \le 10^9~).

~q~ dòng tiếp theo, dòng thứ ~j~ chứa một số nguyên ~k_j~ (~k_j \le n~) thể hiện truy vấn thứ ~j~.

Output

Gồm ~q~ dòng, dòng thứ ~j~ in ra một số nguyên duy nhất là số dãy con tăng có độ dài đúng bằng ~k_j~, vì kết quả có thể rất lớn nên hãy lấy số dư khi chia cho ~10^9 + 7~.

Sample Input

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

Sample Output

6
10
6
1

Subtasks

Subtask 1 (40%): ~n, q \le 20~.

Subtask 2 (60%): Không có ràng buộc gì thêm.

TaThanHungBC là một cậu bé rất thông minh và tinh nghịch. Hôm nay cậu được mẹ mua cho một mảnh giấy màu có kích thước ~n \times m~.

Là một người nghệ sĩ thực thụ, TaThanHungBC luôn hướng tới sự hoàn hảo, cụ thể cậu định nghĩa một mảnh giấy ~x \times y~ là hoàn hảo nếu như ~\frac{x+y}{2} = \sqrt{x \times y}~.

TaThanHungBC có thể dùng kéo để cắt một mảnh giấy ra thành hai mảnh giấy khác. TaThanHungBC muốn sao cho sau khi hoàn thành cắt thì mọi mảnh giấy đều là hoàn hảo. Tuy nhiên do quá bạn chơi Genshin nên TaThanHungBC muốn cắt ít lần nhất có thể. Bạn hãy giúp TaThanHungBC tìm ra số lần cắt ít nhất có thể.

Tuy nhiên, TaThanHungBC không biết kích thước chính xác kích thước của mảnh giấy mẹ mua cho cậu. Nên cậu sẽ đặt ra cho bạn ~T~ giả định, giải định thứ ~i~ hỏi xem nếu mẹ cậu mua mảnh giấy kích thước ~n_i \times m_i~ thì cậu sẽ cần cắt ít nhất bao lần?

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ là số giả định.
• ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~n, m~ tương ứng với một giả định.

Output

• Đưa ra ~T~ dòng, dòng thứ ~i~ tương ứng với đáp án của giả định thứ ~i~.

Constraint

• ~T \le \mathord{?} \mathord{?} \mathord{?}~
• ~n_i, m_i \leq 500~ ~\forall 1 \leq i \leq T~

Subtask

• Subtask 1 (10%): ~T = 1~, ~n, m \leq 20~.
• Subtask 2 (20%): ~T = 1~, ~n, m \leq 500~.
• Subtask 3 (30%): ~n, m \leq 20~.
• Subtask 4 (40%): không có giới hạn gì thêm.

Sample Input

2
3 5
3 3

Sample Output

3
0

Note

Cách cắt của giả định ~1~.