Mirza is a fresher of IUT (International University Of Technology). Today is his fresher's reception day. His senior brother's arranged an amazing function on that occasion. N best music bands of the country came to perform in his campus. As per sunset rules, they had to shorten the timespan of the program. So, all the N bands are performing in different auditoriums at the same time. After each song of each band there is a break, when if you wish you can go from one auditorium to other, but not in between the songs. And also you want to enjoy the most.

Now, there is a fun value for each song played by each band. When you are listening to a band for the first time, you'll enjoy the most. Then if you hear a song for the second time you'll enjoy less. The value will decrease by times.

More formal: for a specific band i, There is two fun coefficients a_i and b_i. While listening a song of a particular band for the k-th time, Mirza gains a enjoyment value of  f(i, k) = a_i − (k − 1)² * b_i. If f(i, k) is non-positive, listening a song to that band is no longer enjoyable. Note: If you enjoyed 1st song of a band then go to other auditorium and miss the second song of this band and come back again for the 3rd song, the 3rd song of this band will count as 2nd for you as you are listening them for the 2nd time.

Given the maximum time Mirza can spend in the auditoriums, can you tell the maximum enjoyment value of Mirza.

Input

The first line contains the integer N, where N is the number of band came to perform (0 < N ≤ 100). The following N lines contain the integers a_i, b_i and t_i where a_i and b_i are the fun coefficients as specified above and t_i is the length of each song played by the i-th band (0 ≤ a_i ≤ 2500; 0 ≤ b_i ≤ 2500; 0 < t_i ≤ 50000). The next line contains a positive integer Q denoting the number of Query (0 ≤ Q ≤ 1000). Each of the following Q lines contains an integral time T that Mirza spends in auditorium his (0 ≤ T ≤ 50000).

Output

For each query, print an integer denoting the maximum enjoyment value Mirza can get.

Example

Input:
2
5 0 5
7 0 7
4
88
5
6
7

Output:
88
5
5
7

Input:
1
100 3 2
5
2
3
4
5
100

Output:
100
100
197
197
435