Problem Description

Lines are of single-dimension.
Surfaces are of double-dimension.
Cubes are of triple-dimension.
Jesus is of four-dimension.

Jesus told you that: I do not want to stay in the four-dimensional space but N-dimensional space instead. However, I do not know what the N-dimensional space is like, and therefore I need your help. I want to know the Union of the (length or area or volume, etc) of M N-dimensional object. You have to calculate the number.

Input

There are several test cases in the input.

The first line includes two positive integer M and N (1 ≤ N ≤ 10, 1 ≤ M ≤ 100) indicating there are M N-dimensional objects.
The following 2M lines describe M N-dimensional objects.
For each subject, there are two lines:
The first line contains N integers describing a corner.
The second line contains N integers describing the opposite corner.
You can assume all coordinates are no more than 10^9.

The input terminates by end of file marker.

Output

For each test case, output an integer, indicating the union (length or area or volume, etc), because the result maybe very large, so just mod 14121413.

3 2
3 3
8 10
2 2
3 3
0 0
1 8

44

Hint

Happy birthday to DaoThree!

Author

DaoThree@WHU