Dino và Daisy đang chơi một trò chơi, ban đầu Dino có ~A~ điểm và Daisy có ~B~ điểm. Mỗi phút, mỗi bạn được tăng lên ~1~ điểm. Hỏi sau bao nhiêu phút thì số điểm của Dino gấp ~3~ lần số điểm của Daisy? Nếu điểm của Dino không thể gấp ~3~ lần điểm của Daisy thì in ra NO.

Input

• Dòng ~1~ chứa một số tự nhiên ~A~ là số điểm ban đầu của Dino;
• Dòng ~2~ chứa một số tự nhiên ~B~ là số điểm ban đầu của Daisy.

Output

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

Example

Sample input 1

9
1

Sample output 1

3

Giải thích

Sau 3 phút thì số điểm của Dino là ~9+3=12~, điểm của Daisy là ~1+3=4~. Khi đó điểm của Dino gấp ~3~ lần điểm của Daisy.

Sample input 1

4
2 

Sample output 1

NO

Giới hạn

• Nếu chương trình chạy đúng những trường hợp ~A, B \leq 1000~, thí sinh sẽ được ~60~ điểm;
• Nếu chương trình chạy đúng những trường hợp ~A, B \leq 10^9~, thí sinh sẽ được ~100~ điểm;

Một câu chuyện rất dài... thầy đã xoá đi...

Quân Quần Què đã trao tận tay thông điệp của Bảo Bay Bổng cho các em như đã hứa, nội dung của nó là: Bảo Bay Bổng viết xâu BAOBAYBONG vô hạn lần lên mảnh giấy. Các kí tự trong xâu anh viết được đánh số từ ~1~. Hỏi trong đoạn ~[l, r]~ có bao nhiêu chữ B.

Input

• Gồm một dòng là hai số nguyên ~l, r~.

Output

• In ra một số nguyên là đáp án của bài toán.

Điều kiện

• ~1 \le l \le r \le 10^{18}~.

Subtask

• ~40\%~ số điểm: ~r \le 10^6~.
• ~30\%~ số điểm: ~l = r~.
• ~20\%~ số điểm: ~l = 1~.
• ~10\%~ số điểm: Không có ràng buộc gì thêm.

Ví dụ

Input:

1 4

Output:

2

Một câu chuyện rất dài... thầy đã xoá đi...

~n~ lon nước tăng lực của mrtee có độ phê lần lượt là ~a_1, a_2, \ldots, a_n~. Ban đầu, mrtee có sức hấp thụ dinh dưỡng là ~k~. Khi mrtee chuẩn bị uống một lon nước tăng lực, thầy sẽ phải vận nội công khiến cho ~k~ giảm đi ~1~ đơn vị. Và khi uống lon nước đó, mrtee sẽ được ~a_i \times k~ năng lượng. Mỗi lon chỉ được sử dụng tối đa ~1~ lần.

Giống như bao người khác, mrtee cũng có ngưỡng giới hạn cho sự tích trữ năng lượng của mình. Do đó, mrtee muốn đặt ra ~q~ câu hỏi. Trong mỗi câu hỏi, mrtee đưa ra một giá trị ~x~ và muốn bạn hãy tính xem mrtee có thể uống nhiều nhất bao nhiêu lon nước tăng lực sao cho tổng năng lượng thu được không vượt quá ~x~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, k~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~.
• Dòng thứ ba chứa số nguyên dương ~q~.
• ~q~ dòng cuối cùng, mỗi dòng chứa một số nguyên dương ~x~ đại diện cho một câu hỏi của mrtee.

Output

• Với mỗi câu hỏi, in ra một số nguyên không âm là kết quả của câu hỏi đó.

Điều kiện

• ~1 \le n \le k \le 10^5~.
• ~1 \le q, a_i \le 10^5~.
• ~1 \le x \le 10^{16}~.

Subtask

• ~25\%~ số điểm: ~n, q \le 10~.
• ~25\%~ số điểm: ~n, q \le 10^3~.
• ~25\%~ số điểm: Tất cả lon nước có độ phê bằng nhau.
• ~25\%~ số điểm: Không có ràng buộc gì thêm.

Ví dụ

Input:

3 5
3 2 4
4
1 13 17 100

Output:

0
1
2
3

Mrtee đang lặn lội trên con đường tìm ma pháp sư Marisa thì có một con Rùa và một con Thỏ cãi nhau xem ai nhanh hơn. Chúng quyết định giải quyết việc tranh luận bằng một cuộc thi chạy đua. Chúng đồng ý lộ trình và bắt đầu cuộc đua.

Thỏ xuất phát nhanh như tên bắn và chạy thục mạng rất nhanh, khi thấy rằng mình đã khá xa Rùa, Thỏ nghĩ nên nghỉ cho đỡ mệt dưới một bóng cây xum xê lá bên vệ đường và nghỉ thư giãn trước khi tiếp tục cuộc đua.

Vì quá tự tin vào khả năng của mình, Thỏ ngồi dưới bóng cây và nhanh chóng ngủ thiếp đi trên đường đua. Rùa từ từ vượt qua Thỏ và sớm kết thúc đường đua.

Khi Thỏ thức dậy thì rùa đã đến đích và trở thành người chiến thắng. Thỏ giật mình tỉnh giấc và nhận ra rằng nó đã bị thua.

Không thể chấp nhận sự thật, Thỏ quyết định tái đấu. Lần này, thay vì dùng một trò thiên về sức lực, Thỏ quyết định thách đấu bằng cách đố Rùa một câu hỏi đầy hóc búa.

Cho đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh, không có khuyên và cạnh lặp.

Để tạo ra được một đồ thị có độ đẹp, ta cần điền các số nguyên dương ~c~ trên mỗi đỉnh (~c~ chỉ có thể là ~1~, ~2~, hoặc ~3~), sao cho với mỗi cạnh, tổng của hai số được điền trên ~2~ đỉnh được kết nối bởi cạnh đó là một số lẻ.

Thỏ đố Rùa có thể đếm số cách để điền các số ~1,2,3~ lên mỗi đỉnh sao cho tạo ra được một đồ thị đẹp. Do con số này có thể rất lớn, hãy in nó ra theo ~modulo~ ~998244353~.

Lưu ý: Rùa phải điền đúng một số trên mỗi đỉnh.

Để cho câu đố thêm phần học búa, Thỏ sẽ hỏi ~q~ câu có dạng như vậy.

Rùa dù là một sinh vật cute nhưng không giỏi đồ thị cho lắm, hãy giúp Rùa hoàn thành bài toán này nhé!

Input

• Dòng đầu tiên gồm số nguyên dương ~q~ miêu tả số câu hỏi.
• Đối với mỗi câu hỏi:
  • Dòng đầu tiên ~2~ số nguyên dương ~n,m~ miêu tả số đỉnh và cạnh của đồ thị.
  • ~m~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~u_i,v_i~ ~(1 \le u_i,v_i \le n, u_i \neq v_i)~ miêu tả cạnh thứ ~i~.

Output

• Với mỗi câu hỏi, in ra một dòng là số nguyên duy nhất là số cách điền thỏa mãn sau khi lấy phần dư cho ~998244353~.

Điều kiện

• ~1 \le q \le 3 \times 10^5~.
• ~1 \le n,m \le 3 \times 10^5~.
• Dữ liệu đảo bảo rằng tổng ~n~ trong tất cả các câu hỏi không vượt quá ~3 \times 10^5~, tương tự với tổng ~m~.

Subtask

• ~50\%~ số điểm: ~n \le 10, q \le 10~.
• ~30\%~ số điểm: Trong mọi câu hỏi, đồ thị có dạng cây.
• ~20\%~ số điểm: Không có ràng buộc gì thêm.

Ví dụ

Input:

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

Output:

0
4

Giải thích:

Ở câu hỏi đầu tiên, không có cách điền nào thỏa mãn.

Ở câu hỏi thứ hai, có ~4~ cách điền như sau:

• Điền số ~1~ vào đỉnh ~1~, số ~2~ vào đỉnh ~2~.
• Điền số ~3~ vào đỉnh ~1~, số ~2~ vào đỉnh ~2~.
• Điền số ~2~ vào đỉnh ~1~, số ~1~ vào đỉnh ~2~.
• Điền số ~2~ vào đỉnh ~1~, số ~3~ vào đỉnh ~2~.

Một câu chuyện rất dài... thầy đã xoá đi...

Thử thách mà Marisa đặt ra cho Pikachu chính là phải chặt các cây Yutam. Các cây Yutam xếp thành một hàng gồm ~n~ cây với các độ cao phân biệt. Marisa yêu cầu Pikachu không được chặt cây số ~1~ bởi vì đây là cây mà Marisa cần dùng để làm nhiên liệu cho Opium.

Mỗi ngày, Pikachu sẽ đi qua tất cả các cây và đánh dấu những cây mà thấp hơn cây đằng trước nó. Sau đó, Pikachu sẽ chặt tất cả các cây được đánh dấu rồi đi về. Nếu anh làm khác thì rất có thể sẽ bị dính độc của Yutam.

Vì muốn cứu người bạn Bubu của mình, hãy cho Pikachu biết anh cần ít nhất bao nhiêu ngày để hàng cây không còn cây nào có thể chặt nữa. Biết rằng trong thời gian Pikachu chặt, Marisa đã làm phép để các cây không mọc thêm.

Input

• Dòng đầu tiên chứa số tự nhiên ~n~.
• Dòng tiếp theo chứa ~n~ số nguyên dương phân biệt ~h_1, h_2, \ldots, h_n~ là chiều cao của các cây.

Output

• In ra một số nguyên là đáp án của bài toán.

Điều kiện

• ~1 \le n \le 2 \times 10^6~.
• Chiều cao các cây không vượt quá ~10^9~.

Subtask

• ~50\%~ số điểm: ~n \le 1000~.
• ~30\%~ số điểm: ~n \le 5 \times 10^5~.
• ~20\%~ số điểm: Không có ràng buộc gì thêm.

Ví dụ

Input:

4
1 3 2 4

Output:

1

Kirisame Marisa là một ma pháp sư dị thường sống trong rừng Ma Thuật. Dị thường hơn nữa là mặc dù có nghề nghiệp là một ma pháp sư, cô thật ra là một con người bình thường.

Những ma thuật của cô thật sự rất sặc sỡ, nhưng việc sử dụng nó lại rất đơn giản.

Trước hết, cô tìm kiếm những cây nấm ma để làm nhiên liệu ma thuật, và phải thu hái nấm ở những nơi mà chúng mọc ổn định. Tiếp đến cô luộc chúng và nấu súp bằng một công thức bí mật trong vài ngày sau đó. Trong những ngày kế tiếp cô sẽ tiến hành pha trộn một số loại súp nấm với nhau, sau đó sấy khô chúng thành dạng rắn. Cuối cùng chúng đã sẵn sàng cho các thí nghiệm ma thuật. Cô sẽ thực hiện đủ kiểu thí nghiệm khác nhau, bao gồm nén lại thành cục và ném đi, đun nóng chúng hoặc hòa chúng vào dòng nước chảy trên núi. Rất rất hiếm khi cô tìm thấy được một loại ma thuật thực sự từ những thí nghiệm này.

Mọi lần thành công hay thất bại đều được cô ghi chép lại, trước khi bắt đầu cuộc hành trình đi tìm nấm mới.

Cô nói mình dùng đủ loại ma thuật, nhưng như thế không có nghĩa là cô dùng được nhiều loại ma thuật đa dạng.

Ma thuật của cô không có hiệu lực nào khác ngoài sức công phá, vậy nên hầu như chỉ có thể nhờ vả cô trong việc trừ yêu quái. Tuy vậy, ma thuật của cô có ít nhược điểm và cho hiệu quả như nhau đối với bất kỳ ai từ con người cho tới yêu quái, thế nên xét về sức phá hoại thuần túy (so với con người) thì không ai hơn được cô.

Nhưng gần đây, trong quá trình điều chế nấm, cô thu được một chất có tác dụng lên hệ thần kinh trung ương gây cảm giác như giảm đau, hưng phấn hay cảm thấy dễ chịu... mà khi dùng nhiều lần thì sẽ phải sử dụng lại nó nếu không sẽ rất khó chịu. Cô đã nghĩ đây là một phế phẩm nhưng bằng một cách nào đó, các học sinh ở Tuyển Tin Hà Nội Cánh Tay lại có vẻ đam mê với loại hợp chất mới này, chính thế cô đã đặt tên nó là Opium. Cô trồng một loại cây đặc biệt có thể tạo ra Opium trong khu rừng kì bí và bắt đầu bán cho các bạn học sinh ở Tuyển Tin.

Một ngày nọ, một người từng được cô cứu là Pikachu lại tới cầu cứu cô. Anh ta nói rằng chú chó của anh là Bubu đã hít phải độc từ một loài cây mà các thợ săn thường gọi là cây Yutam. Khi nghe Pikachu tả loại cây đó, cô lập tức nhận ra đó là cây Opium của mình. Ngạc nhiên khi Opium lại nguy hiểm đến vậy, cô lập tức yêu cầu Pikachu chặt các cây Opium đó.

Khi Pikachu vẫn đang bận chặt cây thì mrtee đã tới nhà Marisa, người thầy đáng kính này đã lặn lội cả tháng trời để tới đây. Mrtee kể với Marisa về các học sinh của mình và căn bệnh thèm bulul. Nghe xong câu chuyện của mrtee, Marisa ngẫm một hồi lâu thì bất chợt hỏi: "Thầy tới từ trường nào vậy?". "Trường Hà Nội Cánh Tay", mrtee đáp, "cô có cách nào không ạ?". Marisa giật mình, cô đã hiểu căn bệnh mà các học sinh của mrtee và Bubu bị chính là từ Opium của cô gây ra.

Cô lập tức tìm cách xử lí những rắc rối mà mình đã gây ra. Xui một cái là cô đang có đơn hàng giao Opium cho khách hàng quan trọng. Tuy biết là Opium nguy hiểm, nhưng đây là vị khách đặc biệt và người này không quan tâm tới tác hại của Opium.

Vì muốn cứu học sinh của mình thật nhanh nên mrtee đã đồng ý giúp Marisa chuẩn bị đơn hàng đó, còn cô sẽ làm thuốc giải.

Hôm nay Marisa có một đơn hàng gồm ~n~ lọ Opium có cân nặng lần lượt là ~A_1, A_2,...,A_n~, cô phải cho các lọ này vào hộp, có tải trọng tối đa là ~l~, theo thứ tự từ ~1~ đến ~n~.

Việc đóng hàng bằng tay rất vất vả nên Marisa đã mua chiếc máy đóng hàng METH-696 của Nitori. Chiếc máy có thể xử lý được ~T~ hộp cùng một lúc. Mỗi một phút, máy có thể thực hiện một trong những thao tác sau:

• Nhét chiếc lọ đang xét vào một trong những thùng đang mở.
• Đóng một thùng đang mở, cất nó đi và thay nó bằng một thùng mới để xử lý tiếp.
• Vứt lọ đang xét đi.

Vì vị khách này khá dễ tính nên Marisa có thế giao thiếu tối đa ~k~ lọ thuốc. Hỏi mrtee cần ít nhất bao nhiêu hộp để xử lý hết ~n~ lọ thuốc trên.

Input

• Dòng đầu chứa 4 số nguyên ~n, l, k, T~.
• Dòng thứ hai chứa n số nguyên ~A_1, A_2,...,A_n~.

Output

• In ra một số nguyên là đáp án cửa bài toán.

Điều kiện

• ~1 \le n, l \le 2000~.
• ~0 \le k \le 5~.
• ~1 \le T \le 2~.
• ~1 \le A_i \le l~.

Subtask

• ~10\%~ số điểm: ~T = 1; k = 0~.
• ~15\%~ số điểm: ~T = 1~.
• ~20\%~ số điểm: ~T = 2; n \le 20; k = 0~
• ~20\%~ số điểm ~T = 2; l \le 20~.
• ~20\%~ số điểm ~T = 2; n \le 69~.
• ~15\%~ số điểm ~T = 2~.

Ví dụ

Input:

9 10 0 1
1 4 6 3 5 2 3 8 4

Output:

5

Input:

6 8 0 2
4 2 5 3 5 4

Output:

3