ยินดีต้อนรับสู่รายการ TV Time ของ Mr. Ant Tenna! ในรอบนี้ของเกม คุณจะได้รับถังน้ำ $n$ ใบ โดยถังใบที่ $i$ มีความจุสูงสุด $v_i$ หน่วยปริมาตรของน้ำ เมื่อเริ่มเกม ถังทุกใบจะถูกเติมน้ำจนเต็ม และภารกิจของคุณคือการกักเก็บน้ำไว้ให้ได้มากที่สุดเท่าที่จะทำได้ในช่วงเวลา $t$ วินาทีถัดไป แต่จุดหักมุมก็คือ ถังเหล่านี้รั่ว! ถังใบที่ $i$ มีอัตราการรั่วไหลเท่ากับ $l_i$ หมายความว่าในทุกๆ วินาทีหลังจากเริ่มเกม ถังใบที่ $i$ จะมีน้ำไหลออก $l_i$ หน่วยปริมาตร
ก่อนที่เกมจะเริ่ม คุณสามารถรวมถังจำนวนเท่าใดก็ได้เข้าด้วยกันเป็นใบเดียว ถังที่ได้จะมีค่าความจุเท่ากับความจุสูงสุดในบรรดาถังที่นำมารวมกัน และมีอัตราการรั่วไหลเท่ากับอัตราการรั่วไหลต่ำสุดในบรรดาถังที่นำมารวมกัน คุณสามารถทำการรวมถังกี่ครั้งก็ได้ แต่ต้องทำก่อนที่จะเติมน้ำลงไป
Tenna ตั้งคำถาม $q$ ข้อ โดยคำถามข้อที่ $i$ มีเวลาจำกัด $t_i$ สำหรับแต่ละ $1 \le i \le q$ จงคำนวณปริมาตรน้ำรวมสูงสุดที่ยังคงเหลืออยู่หลังจากผ่านไป $t_i$ วินาที สังเกตว่าแต่ละคำถามเป็นอิสระต่อกัน
ข้อมูลนำเข้า
มีหลายชุดข้อมูลทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 5 \times 10^4$) แทนจำนวนชุดข้อมูลทดสอบ สำหรับแต่ละชุดข้อมูลทดสอบ:
บรรทัดแรกประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 2 \times 10^5$) แทนจำนวนถังน้ำ
บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$) โดยที่ $v_i$ คือความจุของถังใบที่ $i$
บรรทัดที่สามประกอบด้วยจำนวนเต็ม $n$ จำนวน $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$) โดยที่ $l_i$ คืออัตราการรั่วไหลของถังใบที่ $i$
บรรทัดที่สี่ประกอบด้วยจำนวนเต็ม $q$ ($1 \le q \le 2 \times 10^5$) แทนจำนวนคำถาม
บรรทัดที่ห้าประกอบด้วยจำนวนเต็ม $q$ จำนวน $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$) โดยที่ $t_i$ คือเวลาจำกัดสำหรับคำถามข้อที่ $i$
รับประกันว่าทั้งผลรวมของ $n$ และผลรวมของ $q$ จากทุกชุดข้อมูลทดสอบจะไม่เกิน $2 \times 10^5$
ข้อมูลส่งออก
สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงผลหนึ่งบรรทัดประกอบด้วยจำนวนเต็ม $q$ จำนวนคั่นด้วยช่องว่าง โดยจำนวนเต็มตัวที่ $i$ คือปริมาตรน้ำรวมสูงสุดที่ยังคงเหลืออยู่หลังจากผ่านไป $t_i$ วินาที
ตัวอย่าง
2
4
5 4 7 6
2 1 3 2
3
3 1 2
4
19 47 21 13
5 14 2 3
5
5 2 6 1 4
4 14 8
43 67 38 77 48