Khi còn bé, ai trong chúng ta chẳng từng trải qua trò trốn tìm nghịch ngợm cùng bạn bè khắp xóm. Nhật Tăng cũng vậy: thuở cắp sách đến trường mẫu giáo, cậu thường được chọn làm người đi tìm. Với đôi mắt nhắm chặt, đứng tại gốc cây ưa thích, cậu đếm vang từng tiếng ~5… 10… 15… 20…~ cho đến khi dứt lời, mới mở mắt ra tìm bạn.

Giờ đây, Nhật Tăng lo lắng không biết mình đã đếm đúng các bội số của ~5~ hay chưa. Hãy giúp cậu kiểm tra lại mỗi lần đếm xem có chính xác từ ~5, 10, 15…~ cho đến ~M~ hay không.

Input

• Dòng đầu chứa hai số nguyên dương ~M~ và ~N~ lần lượt là giới hạn đếm số và số lần đếm số của Nhật Tăng ~(M, N \leq 10^3)~.
• Tiếp theo ~N~ dòng, mỗi dòng gồm số nguyên dương ~k~ và ~k~ số nguyên không âm ~A_1, A_2, ..., A_k~ mà Nhật Tăng đã đọc lên ~(A_i \leq M~ và ~k \leq 10^3)~.

Output

• Gồm ~N~ dòng, với mỗi lần đếm in ra:
  • YES nếu dãy đó chính xác là các bội số ~5~ theo thứ tự ~5, 10, 15…~ đến đúng ~M~.
  • NO trong mọi trường hợp còn lại.

Sample Input

20 5
4 5 10 15 20
3 5 10 15
5 5 10 10 15 20
4 5 6 7 8
4 5 15 10 20

Sample Output

YES
NO
NO
NO
NO

Notes

• Lần ~1~: Dãy đủ và đúng thứ tự.
• Lần ~2~: Thiếu số ~20~ cuối cùng.
• Lần ~3~: Thừa một số ~10~ (lặp lại).
• Lần ~4~: Không phải bội số ~5~ ~(6,7,8)~.
• Lần ~5~: Sai thứ tự.

Trong thế giới của những ẩn số và biểu tượng, có một dãy ký hiệu gọi là mảng ~A~ gồm ~N~ phần tử, được định danh bằng các số nguyên theo một trình tự mà nguồn gốc của nó đã bị lãng quên qua thời gian. Nhiệm vụ của bạn là tìm ra cách chia dãy số này thành ít nhất 2 mảnh ghép, mỗi mảnh gồm các phần tử liên tiếp, và các mảnh đều có số lượng phần tử bằng nhau và lớn hơn ~1~. Song, dưới lớp vỏ của yêu cầu đơn giản ấy ẩn chứa một điều khắc nghiệt: sự chênh lệch giữa các tổng số của mỗi mảnh phải được cân chỉnh đến mức tối thiểu, như thể mỗi mảnh đang cạnh tranh để chứng minh giá trị của chính mình.

Yêu cầu: Hãy phân tách mảng ~A~ thành cách mảnh nhỏ, sao cho sự chênh lệch lớn nhất giữa các tổng của mỗi mảnh là nhỏ nhất. Nếu có nhiều cách chia để đạt giá trị nhỏ nhất, hãy đưa ra một phương án bất kì.

Input

• Dòng đầu tiên: Gồm số nguyên dương ~N~ ~(N \leq 10^6)~.
• Dòng tiếp theo: Gồm ~N~ số nguyên của mảng ~A~ lần lượt là ~A_1, A_2, ..., A_N~ ~(|A_i| \leq 10^9)~.

Output

• Dòng đầu tiên: Gồm một số nguyên là sự chênh lệch nhỏ nhất.
• Dòng thứ hai: Gồm một số nguyên là số phần tử của mỗi mảnh ghép.
• Các dòng sau: Mỗi dòng gồm các phần tử thuộc của từng mảnh.

Sample Input

6
1 0 2 0 0 2

Sample Output

1
3
1 0 2
0 0 2

Notes

• Có hai cách chia thoả mãn đạt được sự chênh lệch nhỏ nhất là ~1~ lần lượt là:
  • Cách ~1~: ~[1, 0]~, ~[2, 0]~ và ~[0, 2]~.
  • Cách ~2~: ~[1, 0, 2]~ và ~[0, 0, 2]~.
• Bạn có thể chọn một trong hai cách trên đều thoả mãn yêu cầu bài toán.

Minh là một kỹ sư trẻ đầy nhiệt huyết, luôn ấp ủ ước mơ sở hữu một tổ ấm riêng. Sau nhiều năm tích lũy kinh nghiệm và tích góp, anh quyết định sẽ hiện thực hoá giấc mơ "an cư" chỉ trong ~M~ tháng tới. Để làm được điều đó, Minh xác định phải có tối thiểu ~N~ đồng trong tài khoản tiết kiệm vào cuối kỳ hạn.

Mỗi tháng, Minh dành ra một khoản tiền cố định ~X~ đồng để gửi tiết kiệm. Đặc biệt, anh được phép linh hoạt lựa chọn kỳ hạn gửi (từ ~1~ đến ~12~ tháng) cho mỗi lần gửi. Khi sổ tiết kiệm đáo hạn, toàn bộ gốc lẫn lãi sẽ được chuyển về tài khoản thanh toán rồi ngay lập tức gửi tiếp với kỳ hạn mới mà anh tự chọn.

Bảng lãi suất theo kỳ hạn (tính trên năm, áp dụng cho toàn bộ số tiền trong sổ khi đáo hạn)

Yêu cầu: Hãy tính số tiền ~X~ nhỏ nhất mà Minh cần gửi hàng tháng để đảm bảo rằng sau đúng ~M~ tháng, tổng số tiền tích lũy (bao gồm gốc và lãi) đạt ít nhất ~N~ đồng.

Input

• Dòng đầu: Gồm hai số nguyên ~N~ và ~M~ ~(N \leq 10^{15}, M \leq 10^3)~.

Output

• In ra một số thực – giá trị ~X~, làm tròn đến ~4~ chữ số sau dấu phẩy.
• Output sai số tương đối cho phép: ~10^{–2}~.

Sample Input

70000 4

Sample Output

17356.9857

Nhật Tăng là một sinh viên công nghệ thông tin tại trường đại học Quốc tế Miền Đông. Tại ngôi trường hiện đại tiên tiến này, cậu đã cùng bạn tạo ra trò chơi nhập vai đối kháng có tên Chiến đấu thắng quái vật. Trong trò chơi này, người chơi điều khiển đội gồm ~N~ nhân vật, mỗi nhân vật sẽ có lượng ~HP~ (máu) và ~ATK~ (sức mạnh tấn công). Ở trận đấu thứ i, các nhân vật sẽ tấn công để tiêu tiêu diệt quái vật thứ i. Bắt đầu trận đấu, các nhân vật sẽ được khôi phục lượng ~HP~ ban đầu, người chơi sẽ chọn các nhân vật còn sống ~(HP > 0)~ để tấn công quái vật.

Mỗi lượt chiến sẽ được diễn ra như sau:

• Quái vật bị giảm ~HP~ theo ~ATK~ của nhân vật.
• Sau đó nếu quái vật còn sống, nhân vật bị giảm ~HP~ theo ~ATK~ của quái vật.

Mục tiêu của mỗi trận đấu là tiêu diệt quái vật ~(HP = 0)~ với số lượt tấn công tối thiểu. Nếu không thể hạ gục quái vật bằng các nhân vật, in ra impossible.

Input

• Dòng đầu: Gồm hai số nguyên ~N~ ~(N \leq 10^5)~ và ~M~ ~(M \leq 100)~ lần lượt là số lượng nhân vật và số trận đấu.
• ~N~ dòng sau: Mỗi dòng gồm hai số nguyên dương ~A_i~ và ~B_i~ tương ứng với ~HP~ và ~ATK~ của nhân vật thứ ~i~ ~(A_i, B_i \leq 10^{18})~.
• ~M~ dòng tiếp: Mỗi dòng gồm hai số nguyên dương ~C_j~ và ~D_j~ cho ~HP~ và ~ATK~ của quái vật thứ ~j~ ~(C_i, D_i \leq 10^{18})~.

Output

• In ra ~M~ dòng: Số lượt tấn công tối thiểu để tiêu diệt quái vật, hoặc impossible nếu không thể chiến thắng.

Sample Input

4 2
15 10
9 15
10 3
7 4
49 5
50 10

Sample Output

4
impossible

Notes

• Trận ~1~:
  • Lượt ~1~: Chọn nhân vật ~2~
    • Gây ~15~ sát thương lên quái vật, ~HP~ của quái vật còn ~34~.
    • Nhân vật ~2~ nhận lại sát thương ~5~, ~HP~ của nhân vật còn ~4~
  • Lượt ~2~: Chọn nhân vật ~1~
    • Gây ~10~ sát thương lên quái vật, ~HP~ của quái vật còn ~24~.
    • Nhân vật ~1~ nhận lại sát thương ~5~, ~HP~ của nhân vật ~1~ còn ~10~.
  • Lượt ~3~: Chọn nhân vật ~2~
    • Gây ~15~ sát thương lên quái vật, ~HP~ của quái vật còn ~9~.
    • Nhân vật ~2~ nhận lại sát thương ~5~, ~HP~ của nhân vật còn ~0~ (nhân vật ~2~ đã chết).
  • Lượt ~4~: Chọn nhân vật ~1~
    • Gây ~10~ sát thương lên quái vật, ~HP~ của quái vật còn ~0~ (quái vật đã chết).
  • Tổng sát thương là ~50~ ~→~ đủ để hạ quái vật. Tổng số lượt tấn công là ~4~.
• Trận ~2~:
  • Dù dùng tất cả các nhân vật, tổng sát thương không đủ hoặc họ chết trước khi gây đủ sát thương ~→~ không thể tiêu diệt ~→~ impossible.

Từ lâu, tại vương quốc Brainrot, người ta truyền tai nhau về một dòng dõi thuần tinh tinh – dòng họ Chimpanzee. Theo sử sách, tổ tiên của Chimpanzee đã từng giúp thần Nông bội thu muôn vườn, khiến đất đai trù phú, dân chúng ấm no.

Chimpanzinni Bananinni, chú tinh tinh đời thứ ~97~ trong dòng tộc, sinh ra dưới ánh trăng bạch kim trên đỉnh núi Siêu Chuối. Ngay từ nhỏ, Chimpanzinni Bananinni đã thể hiện năng khiếu bắt sóng năng lượng cây trồng: chỉ cần chạm nhẹ là cánh đồng liền tỏa sáng rực rỡ. Khi lớn lên, Chimpanzinni Bananinni rời núi, lang thang khắp nơi để tìm kiếm thử thách mới.

Một ngày nọ, Chimpanzinni Bananinni đến Trại Chuối Ngự – nơi sở hữu hàng ~n~ cây chuối chứa tinh hoa thần nông, mỗi cây thứ ~i~ ẩn chứa ~a_i~ quả chuối ngự tinh túy. Trại do phù thủy Tung Tung Tung Sahur cai quản, người đã đặt ra bài toán không đơn giản:

• Muốn khai thác tinh hoa, người hái phải tuân theo Lời Nguyền Chu Kỳ:
  • Chỉ được phép hái chuối tối đa ở ~k~ cây liên tiếp.
  • Sau đó phải bỏ qua (không hái) ít nhất ~k~ cây tiếp theo để đất đai hồi sinh, nếu không linh hồn của Tralalero Tralala sẽ trỗi dậy và trừng phạt.

Yêu cầu: Hiện nay Chimpanzinni Bananinni cần một chiến lược thông minh để thỏa mãn Lời Nguyền Chu Kỳ mà vẫn thu thập được nhiều quả chuối ngự nhất. Bạn hãy đồng hành cùng Chimpanzinni Bananinni để tìm ra chiến lược đó.

Input

• Dòng đầu: số testcase ~T~ ~(T \leq 10)~.
  • Mỗi testcase gồm:
    • Dòng ~1~: Chứa hai số nguyên ~n, k~ lần lượt là số lượng cây chuối và giới hạn hái - bỏ qua ~(k \leq n \leq 10^6)~
    • Dòng ~2~: Gồm ~n~ số nguyên không âm ~a_1, a_2, \dots, a_n~ lầ lượt là số lượng quả chuối ở cây thứ ~i~ ~(a_i \leq 10^9)~.

Output

• Gồm ~T~ dòng, mỗi dòng là số quả chuối ngự tối đa Chimpanzinni Bananinni thu được ở testcase tương ứng.

Sample Input

2
7 2
1 1 0 0 0 1 1
9 3
0 0 5 5 0 5 2 3 9

Sample Output

4
22

Notes

• Ở testcase thứ ~2~:
  • Chimpanzinni Bananinni hái ở cây ~3–4~ ~(5 + 5 = 10~ quả~)~
  • Nghỉ không hái ở cây ~5–7~
  • Tiếp tục hái ở cây ~8–9~ ~(3 + 9 = 12~ quả~)~
  • Tổng cộng: ~10 + 12 = 22~ quả chuối ngự.