The fat man came to an open field for a run. People in the field can use k-dimensional integer coordinates to indicate its location. The size of the venue is limited. The size of the i-th dimension is, so the coordinates of the person in the venue should satisfy .

Fatty intends to start from a new location in the venue every day in the next times ,Start running.

The fat man travels according to the pre-defined route every day. The daily route consists of nn steps. Each step can be expressed by cic_ici and did_idi: If he is currently located at , then he will go to , Where . Little C will continue to repeat this route until he walks out of the field to end the day's plan. (That is, after the nth step, if the fat man is still on the court, he will go back to the 111th step and walk again from the beginning).

The fat man wanted to know how many steps he took after p days.

The first line is two integers n, k separated by a single space. Respectively indicate the number of route steps and field dimensions.
The next line of k integers , separated by a single space, represents the size of the venue.
In the next n lines, each line has two integers  separated by a single space, indicating the direction of each step in turn

Explanation of Example 1：
Starting from (1,1) will take 2 steps, starting from (1,2) will take 4 steps, and starting from (1,3) will take 4 steps.
Starting from (2,1) will take 2 steps, starting from (2,2) will take 3 steps, and starting from (2,3) will take 3 steps.
Starting from (3,1) will take 1 step, starting from (3,2) will take 1 step, and starting from (3,3) will take 1 step.
A total of 21 steps.

Output its value after modulo .

3 2
3 3
1 1
2 -1
1 1

21