A Christmas Pizza Puzzle

All submissions for this problem are available.

This problem was part of the CodeChef April Challenge. All user submissions for this contest problem are publicly available here.

Your grandfather is known in the family for his unconventional sense of humour. Since he made his fortune on the network of pizza parlours^a), he has been giving expensive gifts to the members of the family every Christmas. Receiving the gift, however, always involves solving a more or less fancy mathematical puzzle.

This year, your gift was locked in a safe, self-made by your grandfather. The safe was secured with a two digit code: in order to open it you had to provide the correct integer number from the range [0, 99]. A bit disgruntled that this year's puzzle would apparently be solved with the force (and not even too brute), you were just about to start examining the numbers, when you heard grandfather's voice - "Beware, kid! After two unsuccessful attempts the content will be annihilated!" "Then how am I supposed to solve this, Grandpa?" - you asked. "Go and have a better look at the package" - grandfather replied.

Indeed, at the bottom of the package you found a city map on which were indicated all the pizza parlours belonging to your grandfather, as well as a long sheet of paper with a sequence of positive integers. After analysing the data for a while you realized that the number of integer values is equal to the number of pizza restaurants... Recognizing that you still have too little input, you went to ask grandfather for further guidance.

"Ah, all right, I'll solve the riddle for you" - grandfather relented. "For each pizza parlour you have to draw such an axis-aligned square that it is centered at the restaurant and half of the length of its side is equal to the corresponding value from the sheet. Then you have to count all the streets on the map which intersect with the square, and write down the result of calculations. The result for the last pizza parlour will be your magic number."

You were a bit surprised that grandfather ordered you to draw squares and count streets for all the restaurants (and there were many), since the code would only depend on the last one. Nonetheless you willingly took on the job, drew the square for the last pizza parlour, counted the streets and entered the number. Unfortunately the safe didn't open.

You rushed to grandfather and told him about the first failed attempt. "Oh dear, did I forget to mention?" - the old man was slightly taken aback. "For each restaurant but the first one, you have to modify both its coordinates by bit-xor'ing them with the result of calculations for the directly preceding restaurant, before drawing the square!". Will you be able to claim the gift now? You have only one attempt left!

Input

The first line of input contains two integers n and m (0 ≤ n ≤ 5000, 1 ≤ m ≤ 50000), the number of streets in the capital city and the number of pizza parlours, respectively. The following n lines contain four integers x1, y1, x2 and y2, each (0 ≤ x1, y1, x2, y2 ≤ 1000<). Each of these lines defines the location of one of the streets, with (x1, y1) representing one of the endpoints and (x2, y2) the other one. The streets can be assumed to be straight line segments. Eventually there are m lines with three integers x, y and r each (0 ≤ x, y ≤ 1000, 1 ≤ r ≤ 20). Each of these lines defines x and y coordinates of one of the pizza parlours and the corresponding number from the sheet attached to your gift, respectively.

You may find it useful to know that:

• A street can have identical endpoints^b).
• Any two distinct streets have at most one common point.
• When counting intersecting streets, you should assume that the boundary of the square belongs to the square.
• The configuration of the streets guarantees that any square satisfying 0 ≤ x, y ≤ 1000, 1 ≤ r ≤ 20 will contain at most 99 intersecting streets.
• Your grandfather is 78 and claims that Fortran is the best language for solving his Christmas puzzles.

Output

The output should contain a single integer value - the code that opens the safe.

Example

Input:
5 2
2 2 4 6
2 2 7 4
4 6 7 4
7 4 10 3
7 4 10 5
10 4 2
0 0 1

Output:
2

Notes

a) This should not surprise anyone. As the IT sector is extremely well-developed in Byteland, pizza network owners are among the richest people there.

b) For some inscrutable reasons such streets are called squares. Not to be mixed up with the squares you draw!