Selamat datang di TV Time bersama Mr. Ant Tenna! Pada babak permainan ini, Anda diberikan $n$ ember, dengan ember ke-$i$ memiliki kapasitas maksimum sebesar $v_i$ satuan volume air. Pada awal permainan, semua ember akan diisi penuh dengan air, dan misi Anda adalah mempertahankan air sebanyak mungkin selama $t$ detik berikutnya. Namun ada kejutannya: ember-ember ini bocor! Ember ke-$i$ memiliki laju kebocoran sebesar $l_i$, yang berarti setiap detik setelah permainan dimulai, ember ke-$i$ meneteskan $l_i$ satuan volume air.
Sebelum permainan dimulai, Anda boleh menggabungkan sejumlah ember berapa pun menjadi satu. Ember hasil penggabungan memiliki kapasitas yang sama dengan kapasitas maksimum di antara ember-ember yang digabungkan, serta laju kebocoran yang sama dengan laju kebocoran minimum di antara ember-ember yang digabungkan. Anda dapat melakukan penggabungan sebanyak berapa kali pun, tetapi semuanya harus dilakukan sebelum mengisi air.
Tenna mengajukan $q$ pertanyaan, dengan pertanyaan ke-$i$ memiliki batas waktu $t_i$. Untuk setiap $1 \le i \le q$, hitung total volume maksimum air yang tersisa setelah $t_i$ detik. Perhatikan bahwa setiap pertanyaan bersifat independen.
Masukan
Terdapat beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 5 \times 10^4$) yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:
Baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 2 \times 10^5$), yang menyatakan banyaknya ember.
Baris kedua berisi $n$ bilangan bulat $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), dengan $v_i$ adalah kapasitas ember ke-$i$.
Baris ketiga berisi $n$ bilangan bulat $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), dengan $l_i$ adalah laju kebocoran ember ke-$i$.
Baris keempat berisi sebuah bilangan bulat $q$ ($1 \le q \le 2 \times 10^5$), yang menyatakan banyaknya pertanyaan.
Baris kelima berisi $q$ bilangan bulat $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), dengan $t_i$ adalah batas waktu untuk kueri ke-$i$.
Dijamin bahwa baik jumlah $n$ maupun jumlah $q$ di semua kasus uji tidak akan melebihi $2 \times 10^5$.
Keluaran
Untuk setiap kasus uji, keluarkan satu baris yang berisi $q$ bilangan bulat yang dipisahkan oleh spasi, dengan bilangan bulat ke-$i$ adalah total volume maksimum air yang tersisa setelah $t_i$ detik.
Contoh
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