Lơm mở dây chuyển sản xuất bánh mochi để kiếm thêm tiền mua skin Karthus (chú ý: Lơm chứ không phải Lâm). Một hộp bánh mochi tiêu chuẩn gồm ~n~ cái bánh mochi được xếp trên một hàng dọc gồm ~n~ ô. Tuy nhiên do bận học T5T nên dây chuyền của cậu có đôi chút trục trặc, dẫn đến một hộp mochi có thể thiếu một cái, một vài cái hoặc có thể không có cái bánh nào. Hãy tìm tất cả hộp bánh khác nhau mà dây chuyền sản xuất phế như Swain sp trong tay Lơm có thể tạo ra. Một hộp bánh có thể được biểu diễn bằng một xâu gồm các ký tự ~0~ hoặc ~1~. Ví dụ: hộp ~5~ cái mà chỉ có ô thứ nhất và ô kế cuối có bánh mochi được biểu diễn bằng dãy ~10010~.

Input

Gồm một số nguyên ~n~ (~1 \le n \le 20~) duy nhất thể hiện số mochi trong một hộp.

Output

Gồm nhiều dòng, mỗi dòng chứa một dãy chỉ bao gồm các ký tự ~0~ hoặc ~1~ thể hiện một hộp mochi. Do có nhiều hộp mochi khác nhau có thể được tạo ra nên hãy in ra mỗi hộp đúng một lần và theo thứ tự từ điển tăng dần.

Sample input

3

Sample output

000
001
010
011
100
101
110
111

Chỉ còn vài ngày nữa thôi là chúng ta sẽ đón Tết Nguyên Đán, gia đình của TINEZ đang tất bật chuẩn bị quần áo mới và lên kế hoạch đi du xuân đầu năm. Có ~N~ (~1~ ~\leq~ ~N~ ~\leq~ ~16~) địa điểm mà gia đình của TINEZ muốn đi thăm vào những ngày đầu năm mới này. Mỗi địa điểm chỉ được thăm đúng 1 lần và sau khi thăm hết N địa điểm đó thì cả nhà sẽ quay trở về địa điểm bắt đầu. Giữa 2 vị trí ~u~ và ~v~ (~1~ ~\leq~ ~u~, ~v~ ~\leq~ ~N~) có 1 con đường 2 chiều giữa 2 vị trí đó. Thế nhưng, việc di chuyển giữa 2 địa điểm ~u~ và ~v~ sẽ khiến gia đình của TINEZ tốn ~c_{u,v} = c_{v,u}~ (đồng) (~0~ ~\leq~ ~c_{u,v} = c_{v,u}~ ~\leq~ ~10^6~) tiền đổ xăng để di chuyển qua tuyến đường này. Gia đình của TINEZ đang không biết liệu rằng lượng tiền đổ xăng ít nhất cần phải chi để đi qua tất cả các địa điểm này. TINEZ hiện tại đang bận chơi Tết nên quên hết cách code để tìm ra phương án cho bài toán “hóc búa” này nên anh ấy muốn nhờ bạn giải quyết bài toán này.

Input

• Dòng đầu chứa số nguyên ~N~ là số địa điểm
• ~N~ dòng tiếp theo, mỗi dòng chứa ~N~ số ~c_{u,v}~ là chi phí để di chuyển giữa 2 vị trí ~u~ và ~v~

Output

• Đưa ra 1 số duy nhất chính là chi phí nhỏ nhất để thăm tất cả ~N~ địa điểm sau đó quay về địa điểm bắt đầu

Constraint

• ~1~ ~\leq~ ~N~ ~\leq~ ~16~
• ~1~ ~\leq~ ~u,v~ ~\leq~ ~N~
• ~0~ ~\leq~ ~c_{u,v}~ ~\leq~ ~10^6~

Subtasks

• Subtask 1 (80%): ~N~ ~\leq~ ~10~
• Subtask 2 (20%): ~10~ ~<~ ~N~ ~\leq~ ~16~

Sample Input

4
0 10 15 20
10 0 25 25
15 25 0 30
20 25 30 0

Sample Output

80

Notes

Một phương án đi hết tất cả các địa điểm là: ~1 \to 2 \to 4 \to 3 \to 1~. Và đây cũng là phương án có chi phí nhỏ nhất: ~10 + 25 + 30 + 15 = 80~.

Tháp Hà Nội là một trò chơi kinh điển giúp tăng cường tư duy, kĩ năng và trí nhớ. Trò chơi gồm ~3~ cột được đánh số từ ~1~ đến ~3~ từ trái qua phải, ban đầu ở cột thứ nhất có ~n~ đĩa sắp xếp nhỏ dần từ dưới lên trên, mỗi lần di chuyển bạn chỉ được di chuyển một đĩa nằm trên cùng của một cột bất kí sang một cột khác, đồng thời đảm bảo sau mỗi bước di chuyển, các đĩa nằm trên luôn nhỏ hơn đĩa nằm dưới nó. Hãy viết chương trình thể hiện cách di chuyển tất cả ~n~ đĩa từ cột ~1~ sang cột ~3~ tốn ít số bước nhất.

Input

Gồm một số nguyên duy nhất ~n~ (~1 \le n \le 20~)

Output

Gồm nhiều dòng, dòng thứ ~i~ chứa ~2~ số nguyên ~s, t~ thể hiện phép di chuyển một đĩa từ cột ~s~ sang cột ~t~ ở bước thứ ~i~.

Sample input

3

Sample output

1 3
1 2
3 2
1 3
2 1
2 3
1 3

Xâu đối xứng là một xâu mà khi viết nó đảo ngược lại thì vẫn ra xâu ban đầu. Cho số nguyên chẵn ~n~, hãy in ra tất cả các xâu đối xứng độ dài ~n~ theo thứ tự từ điển, mỗi phần tử của xâu là một chữ cái in thường từ ~a~ đến ~z~.

Input

Gồm duy nhất một số nguyên chẵn ~n~ (~2 \le n \le 8~) thể hiện độ dài của các xâu đối xứng.

Output

Gồm nhiều dòng, dòng thứ ~i~ chứa một xâu đối xứng như yêu cầu của đề.

Subtasks

Subtask 1 (60%): ~n \le 6~.

Subtask 2 (40%): ~n = 8~.

Sample input

2

Sample output

aa
bb
cc
dd
ee
ff
gg
hh
ii
jj
kk
ll
mm
nn
oo
pp
qq
rr
ss
tt
uu
vv
ww
xx
yy
zz

=))))))))))))))))))))))))))))))))))))))))

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~.