Daniel and his friends are geared up and ready to ski, so they exit the lodge and behold the breathtaking mountains of snow before them. The ski resort is renowned for its towering mountains, whose majestic peaks disappear into the ethereal clouds and are said to touch the heavens.

In fact, one ride up on a ski lift can take as long as ~12~ minutes! That's even longer than the Peak2Peak Gondola (located in Whistler, British Columbia), the longest ski lift in the real world, which lasts ~11~ minutes.

There are ~N~ ski lifts in the resort, with the ~i~-th ski lift taking ~a_i~ ~(1 \le a_i \le 12)~ minutes to go one way. Each ski lift only has one cart, which will travel from the bottom to the top, then from the top to the bottom, turning around immediately after reaching either end.

Right now it's 9am, and the cart on the ~i~-th lift initially starts at ~b_i~ ~(0 \le b_i \le a_i)~ minutes way up—heading either up or down. If ~d_i~ is ~1~, then the lift is ~b_i~ minutes up the ride and is travelling upwards, and if ~d_i~ is ~2~, the lift is ~b_i~ minutes up the ride and is travelling downwards. Note that if ~b_i~ is either ~0~ or ~a_i~, the direction does not matter.

Daniel, being the analytical and careful-planning type, will ask ~Q~ questions to plan his skiing itinerary, each of which asks: Given ~t_i~ ~(0 \le t_i \le 10^{12})~ minutes past 9am, how long must he wait for a ski lift to arrive at the top or bottom of its path? If ~s_i~ is ~1~, he wants to know how long it takes for any ski lift to reach the bottom of its path, and if ~s_i~ is ~2~, he wants to know how long it takes for any ski lift to reach the top of its path.

Please help him answer each question.

Constraints

~1 \le Q \le 2 \times 10^5~

~0 \le b_i \le a_i \le 12~

~0 \le t_i \le 10^{12}~

\(d_i, s_i ∈ \{1, 2\}\)

Subtask 1 [30%]

~1 \le N \le 10~

Subtask 2 [70%]

~1 \le N \le 2 \times 10^5~

Input Specifications

The first line contains two integers, ~N~ and ~Q~.

The next ~N~ lines contain three integers each, representing ~a_i~, ~b_i~, and ~d_i~.

The next ~Q~ lines contain two integers each, representing ~t_i~ and ~s_i~.

Output Specifications

For each question, output the time from ~t_i~, in minutes, for any ski lift to reach the bottom (for ~s_i = 1~) or the top (for ~s_i = 2~) of its path.

Sample Input 1

2 4
4 2 1
7 1 2
4 2
6 1
13 2
3 2

Sample Output 1

4
0
5
5

Sample Explanation 1

Query	Explanation	Result
1	The first lift reaches the top at ~t=2~, then the bottom at ~t=6~, before reaching the top again at ~t=10~. The second lift reaches the bottom at ~t=1~, then the top at ~t=8~.	Earliest time a lift arrives is ~t=8~, ~\therefore t-t_i=4~
2	The first lift reaches the top at ~t=2~, then the bottom at ~t=6~. The second lift reaches the bottom at ~t=1~, then the top at ~t=8~, before reaching the bottom again at ~t=15~.	~t-t_i=0~
3	The first lift reaches the top at ~t=18~. The second lift reaches the top at ~t=22~	~5~

The last query was calculated similarly.