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