Như các bạn đã biết, chỉ còn không lâu trước khi đến Trung Thu, vì thế hôm nay, Heo, nhân vật chính của chúng ta, sẽ cùng bạn khám phá những sự tích về Trung Thu của các quốc gia có tổ chức lễ hội vào ngày rằm tháng 8 nhé.

Đầu tiên thì không thể bỏ qua Việt Nam với sự tích Chú Cuội Cung Trăng.

Truyện kể rằng từ thời xa xưa, có một chàng tiều phu tên là Cuội. Một hôm, Cuội vào rừng đốn củi gần một con suối nhỏ thì giật mình trông thấy một cái hang cọp. Phát hiện trong hang chỉ có 4 con cọp con đang vờn nhau, Cuội liền xông tới dùng rìu bổ mỗi con một nhát lăn quay ra đất. Thật không may, cọp mẹ đã trở về. Nghe tiếng gầm kinh người ở sau lưng, Cuội chỉ kịp quăng rìu rồi leo tuốt lên ngọn cây cao.

Từ trên cây, Cuội thấy cọp mẹ đau đớn lồng lộn nhìn những đứa con đã chết. Một lát sau, cọp mẹ lủi thủi bước đến gần chỗ Cuội ẩn náu, đớp một ít lá rồi quay lại nhai và mớm cho con. Thoáng chốc, bốn đứa con đã vẫy đuôi sống lại, khiến cuội vô cùng kinh ngạc. Chờ mẹ con cọp bỏ đi nơi khác, Cuội mới leo xuống tìm cây lạ kia đào lên vác về.

Trên đường về, Cuội bắt gặp một ông lão ăn mày nằm chết vất vưởng bên vệ đường. Cuội không ngần ngại mà lập tức hái lá của cây lạ vừa mới đào được nhai rồi mớm cho ông lão. Như một phép màu, ông lão đã mở mắt ngồi dậy. Thấy có cây lạ, ông liền hỏi chuyện, Cuội cũng sẵn lòng trả lời. Sau khi nghe kể, ông bàng hoàng kêu lên:

~-~ Trời ơi! Cây này chính là cây có phép 'cải tử hoàn sinh' đây. Thật là trời cho con để cứu giúp thiên hạ. Con hãy chăm sóc cho cây nhưng nhớ đừng tưới bằng nước bẩn mà cây bay lên trời đó!

Nói xong ông lão chống gậy đi, còn Cuội mang cây về để trong vườn nhà, luôn nhớ tới lời ông lão, ngày ngày tưới bằng nước giếng trong.

Từ ngày có cây thuốc quý, Cuội cứu sống được rất nhiều người. Hễ ai mà gặp chuyện thì Cuội đều mang lá cây đến tận nơi cứu chữa. Một hôm, khi lội qua sông, Cuội gặp một con chó chết trôi. Thế là Cuội vớt nó lên, mớm lá thuốc cho nó sống lại. Từ đó, Cuội có thêm một con vật tinh khôn làm bạn.

Một ngày nọ, phú ông làng bên hớt hải đến nhờ Cuội cứu giúp con gái bị sẩy chân chết đuối, Cuội đã không chần chừ mà đồng ý. Cô gái được cứu sống, xin được làm vợ chàng, phú ông cũng đồng ý.

Hai vợ chồng Cuội đang có một cuộc sống hòa thuận, ấm êm thì ngày kia, khi Cuội vắng nhà, có bọn giặc đi ngang nhà Cuội. Biết Cuội có cây thuốc quý, chúng bèn chơi xấu, giết vợ Cuội rồi moi ruột vứt ra sông. Cuội về thì vợ đã chết từ bao giờ, đắp bao nhiêu lá thuốc vẫn không sống lại.

Thấy chủ đau buồn, chú chó lại gần tỏ ý hiến ruột của mình. Cuội cũng thử liều lấy ruột chó cho vợ rồi nặn ruột khác cho chó bằng đất, đắp lá thuốc lên. Thế là cả người và vật đều sống nhưng từ đây, vợ Cuội mắc chứng hay quên.

Một buổi chiều, lúc Cuội còn đi đốn củi chưa về, vợ ra vườn, không nhớ lời chồng dặn mà tiểu thẳng vào gốc cây thuốc quý. Vừa tiểu xong, mặt đất rung chuyển, cây đảo mạnh, gió thổi ào ào. Cây thuốc sau đó bật gốc bay lên. Khi này Cuội vừa về đến, thấy cây bay lên nên vội vàng vứt bó củi, nhảy lên toan níu cây lại. Nhưng cây đã bay cao quá đầu người, Cuội chỉ kịp móc rìu vào rễ cây, định lôi xuống, nhưng cây cứ bay lên. Cuội cũng không bỏ cuộc, cứ cố níu mãi, thành ra người và cây đều bay vút lên cung trăng. Từ đấy về sau, người ta vẫn thấy một vết đen hình người ngồi dưới gốc cây mỗi khi nhìn lên mặt trăng.

Sau khi nghe kể chuyện, Heo đã mua một con game lấy ý tưởng từ câu chuyện trên vừa mới phát hành tên là Chuối Cụ: giả lập chú Cuội. Trong game này, một hàng ~n~ bệnh nhân xếp hàng chờ được khám bệnh, bệnh nhân thứ ~i~ cần được đắp lá thuốc trong thời gian ~a_{i}~ thì khỏi bệnh. Tuy nhiên, sau khi chữa cho một bệnh nhân, tình trạng bệnh của các bệnh nhân khác nặng lên nên cần thêm ~c~ đơn vị thời gian để chữa. Heo định chữa cho tất cả bệnh nhân nên do thời gian có hạn, Heo chỉ có thể chữa cho ~1~ đoạn liên tiếp các bệnh nhân từ ~L~ đến ~R~. Hiện Heo đang có ~q~ dự định, mỗi dự định Heo chỉ chữa cho các bệnh nhân trong đoạn từ ~L~ đến ~R~. Với mỗi dự định, bạn hãy giúp Heo tính tổng thời gian cần để chữa bệnh.

Input

Vào từ file văn bản BAI1.inp:

• Dòng đầu chứa ~2~ số nguyên dương ~n~ và ~c~ cho biết số lượng bệnh nhân và thời gian tăng thêm ~(n \le 10^{6}, c \le 10^{9})~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_{i}~ cho biết ban đầu bệnh nhân thứ i cần đắp lá thuốc ~a_{i}~ đơn vị thời gian thì khỏi bệnh ~(a_{i} \le 10^{9})~.

• Dòng thứ ba chứa số nguyên dương ~q~ cho biết số lượng dự định của Heo ~(q \le 10^{6})~.

• ~q~ dòng kế tiếp, mỗi dòng gồm 2 số nguyên ~L_{i}~ và ~R_{i}~ cho biết dự định thứ ~i~ của Heo ~(1 \le L_{i} \le R_{i} \le n)~.

Output

Ghi ra file văn bản BAI1.out:

• Gồm ~q~ dòng, dòng thứ ~i~ là đáp án của dự định thứ ~i~.

Đề bài đảm bảo đáp án không vượt quá kiểu dữ liệu 64-bit.

Scoring

Example

Sample Input 1

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

Sample Output 1

17
30
56

Sample Input 2

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

Sample Output 2

12
14
16
18
20

Truyền thuyết tết Trung Thu ở Nhật Bản kể rằng, loài thỏ vì không kiếm được thức ăn cho một gã ăn xin nên đã nguyện dâng hiến bản thân. Cảm động vì hành động của loài thỏ, gã ăn xin đã biến thành Nguyệt Ông, đưa loài thỏ lên cũng trăng sống với mình. Người Nhật tin rằng, mặt trăng có hình dạng lồi lõm vì loài thỏ ngọc hằng ngày vẫn giã nếp làm mochi ở đấy.

Sau khi nghe về sự tích tết Trung Thu ở Nhật Bản, Heo cảm thấy rất hứng thú với những con thỏ ngọc được kể trong truyện. Heo liền thử nhìn lên mặt trăng. Bất ngờ thay, Heo lại nhìn thấy ~n~ vị trí, được đánh số từ ~1~ đến ~n~. Có ~k~ con thỏ đang giã mochi, con thỏ thứ ~i~ đang giã ở vị trí ~p_{i}~ tại độ cao ~t_{i}~. Heo nhận thấy rằng, độ cao tổng thể tại vị trí ~i~ bất kì sẽ bằng ~\min(t_{j} + |p_{j} - i|)~ với mọi ~j~ từ ~1~ đến ~k~. Nhằm thỏa mãn sự hiếu kì của bản thân, Heo muốn biết độ cao tổng thể tại tất cả vị trí tử ~1~ đến ~n~. Đương nhiên, bạn sẽ là người làm công việc ấy (Vi con Heo nay no luoi vcl).

Input

Vào từ file văn bản BAI2.inp:

• Dòng đầu tiên gồm số nguyên dương ~T~ ~(T\leq2)~ ~-~ Số bộ test.
• Dòng đầu tiên của mỗi test gồm 2 số ~n,k~ ~(1\leq k \leq n \leq 10^{6},~ Tổng ~n~ của các test không vượt quá ~15\times10^{5})~ ~-~ Số vị trí và số con thỏ đang giã mochi.
• Dòng thứ 2 của mỗi test gồm ~k~ số ~p_{1},p_{2},...,p_{k}~ ~(1\leq p_{i}\leq n, p_{i} \neq p_{j}~ với mọi ~i\neq j)~ ~-~ Vị trí của con thỏ thứ ~i~.
• Dòng thứ 3 của mỗi test gồm ~k~ số ~t_{1},t_{2},...,t_{k}~ ~(1\leq t_{i}\leq 10^{9})~ ~-~ Độ cao của con thỏ thứ ~i~.

Output

Ghi ra file văn bản BAI2.out:

• Với mỗi bộ test, in ra ~1~ dòng chứa ~n~ số ~-~ Độ cao tổng thể tại vị trí ~1,2,...,n~.

Scoring

Example

Sample Input

2
5 1
3 
18 
10 4
9 5 10 6 
13 19 8 16 

Sample Output

20 19 18 19 20 
17 16 15 14 13 12 11 10 9 8 

Note

• Cấp số cộng là dãy số thỏa mãn sai khác giữa hai phần tử liên tiếp bất kì là hằng số. Ví dụ như dãy ~(2; 4; 6)~ hay ~(6; 9; 12; 15)~ là cấp số cộng, còn ~(1; 7; 7; 0; 1; 3)~ hay ~(4; 0; 7; 1; 7; 7)~ thì không.
• Cấp số nhân là dãy số thỏa mãn điều điện kể từ phần tử thứ 2 trở đi (nếu có), mỗi số hạng đều là tích của số hạng trước đó với một hằng số. Ví dụ dãy ~(2; 4; 8; 16)~ hay ~(7; 35; 175; 875)~ là cấp số nhân, còn ~(3; 8; 9; 1; 9; 5)~ hay ~(4; 1; 7; 5; 5; 2)~ thì không.

Khi tìm hiểu về những sự tích về Tết Trung thu ở những quốc gia Châu Á, chắc chắn các bạn đã nghe qua về sự tích Hậu Nghệ xạ nhật. Câu chuyện kể lại hồi xưa trên bầu trời có đến 10 mặt trời, khiến cho mặt đất nóng đến mức không thể trồng lúa nữa. Hậu Nghệ đã dùng tài xạ thủ của mình và bắn rơi 9 mặt trời, vì vậy chàng được trao tặng một nơi ở trên mặt trăng hoặc mặt trời, cùng với lọ nước thần giúp trường sinh bất lão. Nhưng rồi vì thương vợ và không muốn bất tử một mình, Hậu Nghệ đã để lọ nước thần lại cho vợ mình, là Hằng Nga.

Heo rất thích câu chuyện này và cũng rất ngưỡng mộ tài năng thiện xạ của Hậu Nghệ nên cậu tức tốc chạy ra gian hàng trò chơi hội chợ để thử ngay tài năng thiện xạ của mình. Nhưng thay vì bắn rơi Mặt Trời, cậu lại bắn rơi… quả bóng nước. Cho ~N~ quả bóng nước được sắp xếp từ 1 đến ~N~. Mỗi quả bóng khi bị bắn rơi sẽ tạo ra loại âm thanh là ~a_{i}~. Heo có ~Q~ dự định, với mỗi dự định cậu sẽ cùng một lúc bắn hết tất cả quả bóng từ đoạn ~L~ đến ~R~. Vấn đề ở đây là, quả bóng khi rơi xuống sẽ tạo ra âm thanh rất lớn. Heo sẽ bị choáng nếu như trong đoạn Heo vừa bắn tồn tại một loại âm thanh có số lượng lớn hơn hẳn tổng số lượng tất cả các loại âm thanh còn lại trong đoạn đang xét. Vì ngày dự thi chọn đội tuyển HSG TP đang cận kề nên Heo không thể để bản thân mình bị choáng được, nếu không thì cậu sẽ ngất xỉu trong lúc đang thi mất! Vì vậy bạn hãy tính giúp Heo (đương nhiên rồi) với mỗi dự định trong tổng số ~Q~ dự định, nếu Heo chọn dự định đó thì liệu cậu sẽ không bị choáng để tham gia kì thi chọn đội tuyển HSG TP chứ?

Input

Vào từ file văn bản BAI3.inp:

• Dòng đầu tiên gồm số nguyên dương ~N~, ~Q~ ~(1\leq N, Q\leq5\times10^{5})~ ~-~ Số lượng bóng nước và số dự định của Heo.

• Dòng thứ 2 của mỗi test gồm ~N~ số ~a_{1}, a_{2},..., a_{N}~ ~(1\leq a_{i}\leq 10^{9})~ ~-~ Loại âm thanh mà quả bóng nước thứ ~i~ sẽ tạo ra khi bị bắn rơi.

• ~Q~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~L~ và ~R~ ~(1\leq L\leq R\leq N)~ là đoạn bóng nước mà Heo dự định bắn rơi.

Output

Ghi ra file văn bản BAI3.out:

• In ra ~Q~ dòng, với mỗi dòng là câu trả lời tương ứng cho từng dự định: in ra "No" nếu sau dự định đó Heo không bị choáng và vẫn có thể tham gia kì thi chọn đội tuyển HSG TP, và "Yes" trong trường hợp ngược lại

Scoring

Example

Sample Input

5 2
1 2 3 2 4
2 4
2 5

Sample Output

Yes
No

Vẫn là câu chuyện Hậu Nghệ xạ nhật, tuy nhiên ở phiên bản này, 9 mặt trời lại là 9 người con của Ngọc Hoàng. Do giết con của Ngọc Hoàng nên từ thần bất tử, Hậu Nghệ và Hằng Nga bị đày xuống hạ giới. Sau vô vàn nỗ lực, Hậu Nghệ đã tìm thấy viên thuốc bất tử và cất trong hộp ở nhà, dặn vợ không được mở ra. Tuy nhiên, cũng như Pandora trong thần thoại Hy Lạp, Hằng Nga đã nhân lúc chồng không có nhà mà lén mở hộp ra. Đúng lúc này, Hậu Nghệ quay về. Sợ chồng phát hiện nên Hằng Nga bỏ luôn viên thuốc vào miệng. Ngay lập tức, Hằng Nga bay lên trời do công hiệu viên thuốc quá mạnh, do chỉ cần nửa viên thì đã có thể bất tử.

Lúc này, Heo nhớ ra trong game Chuối Cụ ở bài 1, để có thể tăng gấp đôi công hiệu của lá thuốc, cậu có thể gacha mở rương hoặc sử dụng gift code. Heo đã dùng toàn bộ số tiền của mình để đi du lịch các nước, tìm hiểu sự tích và chơi các trò chơi nên không thể nạp thêm để gacha như Tuab, nhưng Heo có thể sử dụng một gợi ý của nhà phát hành game để nhập gift code.

Gợi ý của nhà phát hành game gồm một xâu ~S~ chỉ gồm các con số từ ~0~ đến ~9~. Ngoài ra, Heo còn được thưởng thêm ~q~ cặp số ~l~, ~p~. Biết rằng gift code được kích hoạt nếu bạn nhập đúng ~q~ chữ số, chữ số thứ ~i~ là kí tự ~p~ của xâu con~^\dagger~ có thứ tự từ điền lớn nhất của ~S~ trong các xâu con có độ dài ~l~.

Input

Vào từ file văn bản BAI4.inp:

• Dòng đầu chứa xâu ~s~ độ dài ~n~.
• Dòng tiếp theo chứa số nguyên ~q~ ~-~ số lượng truy vấn.
• Trong ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l, p~ mô tả một truy vấn yêu cầu tìm chữ số ~p~ trong xâu đại độ dài ~l~ của ~s~.

Output

Ghi ra file văn bản BAI4.out:

• Ghi ra ~q~ dòng, dòng thứ ~i~ ~(1 \leq i \leq q)~ ghi một chữ số là câu trả lời cho truy vấn thứ ~i~.

Scoring

Example

Sample Input

27122023
5
1 1
2 1
2 2
3 2
4 2

Sample Output

7
7
3
2
2

Note

~\dagger~ Xâu con của một xâu ban đầu có thể thu được bằng cách xóa đi một số kí tự (có thể không xóa) và giữ nguyên thứ tự các kí tự còn lại. Ví dụ ~322095~ là xâu con của ~4253574268526094254~, ~123~ là xâu con của ~123~ nhưng ~213~ không phải là xâu con của ~1231~.

Sau khi dạo chơi một vòng các nước và tìm hiểu về các sự tích, Heo quyết định quay về vì đã bước vào năm học mới. Tuy nhiên, cậu vẫn đang trên mây sau chuyến hành trình vừa rồi nên cậu quyết định đi kể cho các bạn của mình về chuyến đi vừa rồi.

Trong đất nước nơi Heo sống, chuồng nhà của Heo ở thành phố được đánh số ~1~, ~n - 1~ thành phố còn lại được đánh dấu trên bản đồ là thành phố nơi bạn của Heo sống. Heo và các bạn đã thống nhất với nhau để tạo ra một dãy số thần kì ~a~ gồm có ~n~ phần tử (nhấn mạnh đây không phải quà sinh nhật như mấy cái đề nào đó). Để đi từ nhà thứ ~i~ sang nhà thứ ~i + 1~, Heo có thể mở chuyến bay sử dụng chuyên cơ riêng và tốn cố định E năng lượng. Tuy nhiên, với sức mạnh thần kì của dãy số ~a~ bên trên, Heo có thể kích hoạt cổng dịch chuyển tức thời từ vị trí ~i~ đến vị trí ~j~ ~(i < j)~ nếu ~GCD(a_{i}, a_{i + 1}, ..., a_{j})~ ~=~ ~min(a_{i}, a_{i + 1}, ..., a_{j})~ và tốn ~GCD(a_{i}, a_{i + 1}, ..., a_{j})~ năng lượng. Tất nhiên mọi đường đi đều là hai chiều và Heo chỉ tốn năng lượng khi kích hoạt, còn lúc sử dụng thì chỉ việc chill, không tốn năng lượng. Heo muốn kể chuyện cho mọi người bạn của mình nên các bạn hãy giúp Heo xác định năng lượng tối thiểu để Heo có thể đi đến tất cả nhà của bạn mình và trở thành Tourist chính hiệu thay vì chỉ có cái màu.

Input

Vào từ file văn bản BAI5.inp:

• Dòng đầu là số nguyên ~\aleph~ cho biết chỉ số của subtask ~(1 \le \aleph \le 5)~.

• Dòng thứ hai chứa 2 số nguyên dương ~n~ và ~E~ cho biết số lượng thành phố và năng lượng cần để thiết lập chuyến bay bằng chuyên cơ riêng ~(2 \le n \le 10^{6}~, ~1 \le E \le 10^{9})~.

• Dòng thứ ba chứa dãy số thần kì gồm ~n~ số nguyên ~a_{1}, a_{2}, ..., a_{n}~ ~(1 \le a_{i} \le 10^{9})~.

Output

Ghi ra file văn bản BAI5.out:

• Một số nguyên duy nhất là kết quả của bài toán.

Scoring

Example

Sample Input 1

1
5 7
15 2 6 15 8

Sample Output 1

23

Sample Input 2

5
2 1000000000
1000000000 1000000000

Sample Output 2

1000000000

Sample Input 3

5
2 1000000000
5 5

Sample Output 3

5

Sample Input 4

5
2 1000000000
4 7

Sample Output 4

1000000000

Sample Input 5

5
2 99999999
1000000000 1000000000

Sample Output 5

99999999