You have just gotten back a test and, to your disappointment, you notice that you didn't do so well. However, you do know that your teacher is very nice and may only take your grades between a specific time period. You know you did a total of ~N~ assignments ~(1 \le N \le 1000)~, and you're curious about how your grades are. So, you ask your teacher for your grades over the entire semester, as well as how much each grade is worth.

Your teacher, being extremely generous, gives you a list of your grades in percentages, ~g_i~, as well as a list for how much the grade is worth overall in percentage, ~p_i~. It is guaranteed that the sum of all the percentages will add up to 100. These percentages can be between 0 and 100 inclusive. Can you code a program to answer ~Q~ queries ~(1 \le Q \le 10^6)~? Each query will ask for the percentage of your overall mark if only assignments between ~g_L~ to ~g_R~ (inclusive) are included. It is guaranteed that ~(0 \le L \le R)~ and the range is within ~N~.

Remember, to take your overall grade, you will multiply your grade (if it is 88%, put 88) by how much it is worth (if this is worth 30%, put 30) and add up all your assignments. Then, divide the total by your total percentage (if there are assignments with their percentages adding up to 50%, divide by 50) to get the percentage of your overall grade. Remember to times by 30 if the assignment is worth 30%, not 0.3 because this may result in a small difference from the answer when stored.

If a range is full of assignments that are not worth any marks, you will be given a ~100~ since there is nothing to grade.

Input Specification

The first line of the input will contain integer ~N~ and ~Q~, representing the number of assignments you've completed and the number or queries respectively.

The next line will contain ~N~ integers, where each integer represents your grade out of 100.

The following line will contain ~N~ integers, representing the percentage value of each grade that goes towards your overall mark. The sum of all ~N~ integers is guaranteed to be 100.

The next ~Q~ lines will contain integer ~L~ and ~R~, the range of assignments that you want the overall mark for.

Output Specification

For each query, output the overall mark for the assignments between range L and R (inclusive). This mark should be an integer and rounded if it is a decimal.

Try using double instead of float.

Sample Input 1

10 8
80 80 90 90 100 100 30 10 0 100
10 10 7 3 5 0 5 0 30 30
0 9
0 4
5 9
0 0
9 9
2 4
5 6
5 5

Sample Output 1

62
86
48
80
100
93
30
100

Explanation

The first query lets us find the overall mark for all assignments. The sum of all your grades would be ~(80 * 1) + (80 * 1) + (90 * 7) + (90 * 3) + (100 * 5) + (100 * 0) + (30 * 5) + (10 * 0) + (0 * 3) + (100 * 3)~.

Then, we would divide by ~(10 + 10 + 7 + 3 + 5 + 0 + 5 + 0 + 30 + 30)~, which gives us ~61.5%~. Since we round, we print ~62~.

The fourth query has one assignment, which would be ~80%~ since the assignment got a grade of 80%.

The last query has one assignment, which is not worth any marks. This will print out ~100~.

Sample Input 2

2 1
16 83
50 50
0 1

Sample Output 2

50

Explanation

The sum of the grades is ~(16 * 50) + (83 * 50)~. This adds up to ~4950~. When divided by ~(50 + 50)~, we get ~49.5~, which rounds up to ~50~.