B"Qingshan and Daniel are going to play a card game. But it will be so boring if only two persons play this. So they will make n robots in total to play this game automatically. Robots made by Qingshan belong to the team 1 , and robots made by Daniel belong to the team 2 . Robot i belongs to team t_i . Before the game starts, a_i cards are given for robot i . The rules for this card game are simple: We define the distance from robot x to robot y as dist(x,y)=(y-x+n) bmod n . It is similar to the oriented distance on the circle. For example, when n=5 , the distance from 1 to 3 is dist(1,3)=(3-1+5) bmod 5=2 , the distance from 3 to 1 is dist(3,1)=(1-3+5) bmod 5 =3 . Later, Qingshan finds out that it will take so much time to see how robots play. She wants to know the result as quickly as possible. You, as Qingshan's fan, are asked to calculate an array [ans_1,ans_2, ldots,ans_n] -- ans_i is equal to the number of cards, that i -th robot will discard during the game. You need to hurry! To avoid the large size of the input, the team and the number of cards of each robot will be generated in your code with some auxiliary arrays. The first line contains one integer n ( 1 <= n <= 5 cdot 10^6 ) -- the number of robots playing this game. The second line contains one integer m ( 1 <= m <= min(n,200 ,000) ). Each of the next m line contains four integers p_i , k_i , b_i , w_i ( 1 <= p_i <= n , 1 <= k_i <= 10^9+7 , 0 <= b_i ,w_i< k_i ). It's guaranteed that p_m=n and p_{j-1}<p_{j} ( 2 <= j <= m ). Arrays a_j and t_j should be generated by the following pseudo code: Print a single integer <= ft( prod_{i=1}^{n} ((ans_i oplus i^2)+1) right) bmod 10^9+7 , where oplus denotes the bitwise XOR operation. In the first test case a=[5,5,1] and $$"...