Vì hằng năm đều có mùa lũ, quốc hội của đất nước Atlantis đã quyết định xây một công trình ngăn nước có dạng như sau.

Quốc hội sẽ chỉ đạo xây dựng \(N\) vách ngăn. Vách ngăn thứ \(i\) được xây tại vị trí \(P[i]\) và có độ cao \(H[i]\). Để kiểm tra độ hiểu quả của công trình, các đại biểu quyết định thực hiện \(M\) bài kiểm tra. Với mỗi bài kiểm tra, lượng nước \(Q\) sẽ được đổ vào vị trí \(0\). Kết quả được đánh giá bằng cách đếm số lượng bức vách ngăn mà dòng nước đã chảy qua trong bài thử đó.

Công việc xây dựng và việc chỉ đạo các bài kiểm thử đã sẵn sàng đi vào hoạt động. Tuy nhiên các đại biểu quốc hội cần phải chắc chắn rằng không được có một trận lũ nào sẽ đánh chìm quốc gia của họ như lịch sử rất lâu về trước, vì vậy mà họ triển khai rất nhiều đợi thử nghiệm. Bạn là một người kế toán của của dự án kiểm thử trên, hãy viết chương tính kết quả cùa \(M\) lần kiểm thử mà hội đồng yêu cầu.

Dữ liệu:

• Dòng đầu tiên chứa \(1\) số nguyên \(N\) \((1 \leq N \leq 2 * 10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(P[i]\) \((1 \leq P[i] \leq 10^8)\), dữ liệu đảm bảo \(P[i]\) đôi một khác nhau
• Dòng thứ ba chứa \(N\) số nguyên \(H[i]\) \((1 \leq H[i] \leq 10^8)\)
• Dòng thứ tư chứa số nguyên \(M\) \((1 \leq M \leq 2*10^5)\)
• \(M\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(Q\) \((1 \leq Q \leq 10^{16})\)

Kết quả:

• Gồm \(M\) dòng, mỗi dòng chứa duy nhất một số nguyên dương, với mỗi dòng là kết quả khi kiểm thử với lượng nước \(Q\) tương ứng

3
2 6 4 
2 1 3
3
4
5
20

0
1
3

Long là một cậu bé thích ăn bún bò, vì vậy mà nhà Long có nuôi một con mèo. Kì lạ thay, con mèo này lại rất thích chơi oản tù tì với Long.

Luật của trò chơi oẳn tù tì rất đơn giản:

• Kéo (\('K'\)) thắng Lá (\('L'\))
• Lá (\('L'\)) thắng Búa (\('B'\))
• Búa (\('B'\)) thắng Kéo (\('K'\))

Hôm hay Long mới ăn được bát bún bò hơi nhiều ớt, vì vậy rất hăng máu, muốn oản tù tì với con mèo nhà mình tận \(N\) \((N \leq 10^6)\) cho đỡ cay. Mèo ta rất khôn, không chỉ biết rằng Long đang cay mà còn có thể nhìn trước tương lai xem ở bước thứ \(i\) \((1 \leq i \leq N)\) Long sẽ ra \('K'\), \('B'\) hay \('L'\).

Vì đang rất cay nên một số \(K\) \((1 \leq K \leq N)\) xuất hiện lù lù trên mặt Long. Nếu số ván mèo ta oẳn tù tì thắng Long nhiều hơn \(K\) ván thì kiểu gì hôm sau sẽ phải chuyển nhà vào nồi lẩu.

Mặc dù rất sợ nước (đặc biệt là nước sôi) tuy nhiên mèo ta lại rất hiếu thắng, vì vậy mà phải thắng đúng \(K\) ván mới hả hê. Long muốn chơi rất nhiều ván oẳn tù tì, nhiều đến mức nếu đếm bằng cơm thì mèo ta sẽ lên bàn thờ trước khi lên bàn ăn. Vì vậy nó nhờ các bạn, tính số cách mà mèo có thể thắng đúng \(K\) ván khi chơi oẳn tù tì với Long.

Note: vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho \(10^9 + 7\)

Dữ liệu:

• Dòng đầu tiên gồm \(2\) số nguyên dương \(N\), \(K\)
• Dòng tiếp theo gồm xâu \(S\) \((|S| = N)\), kí tự \(S[i]\) sẽ có giá trị là \(1\) trong \(3\) ký tự \('K'\), \('B'\) hoặc \('L'\)

Kết quả:

• Một dòng duy nhất chứa kết quả bài toán, chia lấy dư cho \(10^9 + 7\)

3 1
KBL

12

Bạch Tuộc là con vật có tập tính sống đơn lẻ, vì vậy nó rất cô đơn. Rùa thấy vậy nên thường rủ Bạch Tuộc sang chơi. Tuy nhiên Bạch Tuộc lần nào cũng đến muộn, làm cho buổi gặp mặt không còn vui vẻ nữa. Vấn đề ở đây là, nếu muốn tới nhà Rùa chơi, Bạch Tuộc phải băng qua \(1\) con sông. Rùa thấy vậy nên quyết tâm giúp Bạch Tuộc một phen.

Dòng sông là một ma trận gồm \(n\) hàng và \(m\) cột. Ở cột \(i\) hàng \(j\) chứa một số nguyên là \(a_{i,j}\) là độ sâu của con sông tại vị trí tương ứng. Cột đầu tiên và cuối cùng là hai phía bờ của dòng sông, vì vậy độ sâu sẽ là \(0\).

Rùa có thể chọn hàng thứ \(i\), là các ô \((i, 1), (i, 2), ..., (i, m)\), và xây một cây cầu ngang qua hàng đó. Ở một ô bất kì của hàng, Rùa có thể xây dựng một cọc đỡ cho cầu. Để xây một cọc đỡ ở ô \((i, j)\) thì Rùa sẽ mất chi phí là \(a_{i,j} + 1\). Tuy nhiên, vì hạn chế của vật liệu xây dựng, các cọc đỡ phải thỏa mãn các điều kiện sau:

1. Cọc đỡ phải được xây dựng ở ô \((i, 1)\) và \((i, m)\) (hai bên bờ của dòng sông)
2. Khoảng các giữa \(2\) cọc đỡ bất kì phải nhỏ hơn \(d\). Có nghĩa là cọc đỡ ở ô \((i, j_{1})\) và \((i, j_{2})\) phải có \(|j_{1} - j_{2}| - 1 \leq d\)

Vì xây nếu chỉ xây một cây cầu thì quá nhỏ, không ứng dụng được nhiều. Vì vậy Rùa quyết định xây \(k\) cây cầu liên tiếp. Có nghĩa là Rùa sẽ chọn một hàng \(i\) với \(1 \leq i \leq n - k + 1\), sau đó xây \(k\) cây cầu ở các hàng \(i, i + 1, ..., i - k + 1\).

Để tính được bằng cơm lượng chi phí ít nhất để xây dựng \(k\) cây cầu cần rất nhiều thời gian và công sức. Vì vậy hãy viết chương trình tính giúp Rùa cách thức xây cầu thế nào để tốn ít chi phí nhất.

Dữ liệu:

• Dòng 1 gồm các số nguyên dương \(n, m, k, d\) \((1 \leq k \leq n \leq 100, 3 \leq m \leq 10^4, 1 \leq d \leq m)\)
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(m\) số nguyên dương \(a_{i,j}\) \((1 \leq j \leq m, 0 \leq a_{i,j} \leq 10^6, a_{i,1} = a_{i, m} = 0)\)

Kết quả

• Gồm một dòng duy nhất chứa một số nguyên dương là kết quả bài toán

Example

Test 1

Input

3 11 1 4
0 1 2 3 4 5 4 3 2 1 0
0 1 2 3 2 1 2 3 3 2 0
0 1 2 3 5 5 5 5 5 2 0 

Output

4

Note

Sẽ là tốt nhất khi chọn xây cầu ở hàng 2, cầu sẽ có dạng như sau:

Lưu ý: hình ảnh là mặt cắt ngang của dòng sông, ô màu xám chính là cây cầu, ô màu đen là cọc cầu.

4 5 2 5
0 1 1 1 0
0 2 2 2 0
0 2 1 1 0
0 3 2 1 0

4

Các cọc cầu có thể được đặt trên 2 bên bờ sông, chọn xây 2 cây cầu ở vị trí bất kì đều cần tổng chi phí là 4

Cho hình sau.

Biết độ dài cạnh hình vuông nhỏ là \(a\). Tính diện tích phần được tô đỏ?

Input

• Dòng thứ nhất chứa số nguyên dương \(t\) - số câu hỏi (\(t = 1000\));
• \(t\) dòng tiếp theo, mỗi dòng chứa \(a\) (\(a \leq 10^4\)).

Output

• Ứng với mỗi test là một số thực là đáp án bài toán, sai số không quá \(10^{-6}\).

Note

• Một hằng số hữu ích: \(\pi = 3.14159265358979323846\)

3.14159265358979323846

Example

100

11415.926536