Cho ~n~ đường thẳng có phương trình

~y~ = ~a_i~~x~ + ~b_i~ (~i~ = 1, 2, .., ~n~)

và ~m~ giá trị ~x_1~, ~x_2~,…, ~x_m~

Hãy tính giá trị của hàm:

tại các giá trị ~x~ đã cho

Input:

• Dòng đầu tiên chứa số nguyên dương ~n~ (~n~ ≤ ~10^5~)
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i~,~b_i~ (|~a_i~|,|~b_i~| ≤ ~10^9~)
• Dòng tiếp theo chứa số nguyên dương ~m~ (~m~ ≤ ~10^5~)
• ~m~ dòng cuối cùng, dòng thứ ~i~ chứa số nguyên ~x_i~ (|~x_i~| ≤ ~10^9~ )

Output:

• In ra ~m~ dòng, dòng thứ ~i~ chứa số nguyên ~f~(~x_i~)

Example:

Input

3
1 2
4 6
3 1
3
2 
-10 
100

Output

14
-8
406