Geographer Grigory Georgievich investigates the formation of sand dunes. He chose a very long dune and divided it into a huge number of sections, which he numbered from 1 to 109.
The theory of Grigory Georgievich says that initially the height of the sand relative to some conditional mark in all areas was equal to zero. After that, there were n strong gusts of wind that could change the landscape.
Wind gust number i had the force xi and acted on sections from li-th to ri-th. As a result of this gust, the height of section number li increased by xi, the height of section number li + 1 decreased by xi, the next — increased again by xi, and so on up to section number ri, inclusive.
Knowing all the information about all n gusts of wind, Grigory Georgievich wants to find out the final height of some m sections of interest to him. Help him.
Input data format
The first line of the input file contains two natural numbers n and m (1 ≤ n,m ≤ 1000) — the number of wind gusts and the number of sections, the final height of which is of interest to Grigory Georgievich.
Each of the next n lines contains a description of the next gust of wind — three integers li, ri, xi (1 ≤ li ≤ ri ≤ 109; 1 ≤ xi ≤ 1000).
Each of the next m lines contains an integer qi (1 ≤ qi ≤ 109) — the number of the section for which you want to know its final height. Lot numbers are in ascending order
okay.
Output format
For each of the m queries print one integer — the height of the corresponding section.
Example
Input:
26
1 6 7
3 7 2
1
2
3
6
7