빈 축사 칸

농부 존이 새로 지은 축사는 칸 $N$개가 원형으로 이어진 구조다 ($2 \le N \le 3 \times 10^6$). 칸에는 $0$번부터 $N-1$번까지 번호가 붙어 있고, $N-1$번 칸은 $0$번 칸과 맞닿아 있다.

하루가 끝나면 소가 한 마리씩 축사로 돌아온다. 소마다 들어가고 싶은 칸이 하나 정해져 있다. 그 칸이 이미 다른 소에게 점유되어 있으면, 소는 번호가 커지는 방향으로 칸을 하나씩 살펴보다가 처음 만나는 빈 칸에 들어간다. $N-1$번 칸까지 지나쳤으면 다시 $0$번 칸부터 이어서 살펴본다.

소마다 원하는 칸이 주어질 때, 모든 소가 돌아온 뒤에도 비어 있는 칸 중 가장 작은 번호를 구하자. 답은 소가 돌아오는 순서와 무관하다.

입력이 지나치게 커지지 않도록, 소가 원하는 칸은 $K$개의 줄로 압축해서 주어진다 ($1 \le K \le 10^4$). 각 줄의 형식은 X Y A B다.

이런 줄 하나는 소 $X \times Y$마리가 원하는 칸을 나타낸다. $f(i) = (A \times i + B) \bmod N$이라고 하면, 칸 $f(1), f(2), \dots, f(Y)$를 각각 원하는 소가 $X$마리씩 있다. $A$와 $B$는 $0$ 이상 $10^9$ 이하다.

• 첫째 줄: 정수 $N$과 $K$가 공백으로 구분되어 주어진다.
• 둘째 줄부터 $1+K$번째 줄까지: 각 줄에 위에서 설명한 정수 $X$, $Y$, $A$, $B$가 주어진다. 이 줄들이 나타내는 소는 모두 합쳐 $N-1$마리 이하다. 여러 줄이 같은 칸을 원하는 소를 더할 수도 있다.

• 첫째 줄: 끝까지 비어 있는 칸 중 가장 작은 번호를 출력한다.

예제의 축사에는 $0$번부터 $9$번까지 칸 10개가 있다. 3 2 2 4 줄은 칸 $(2 \times 1 + 4) \bmod 10 = 6$을 원하는 소 3마리와 칸 $(2 \times 2 + 4) \bmod 10 = 8$을 원하는 소 3마리를 나타낸다. 2 1 0 1 줄은 칸 $(0 \times 1 + 1) \bmod 10 = 1$을 원하는 소 2마리를, 1 1 1 7 줄은 칸 $(1 \times 1 + 7) \bmod 10 = 8$을 원하는 소 1마리를 나타내므로 8번 칸을 원하는 소는 모두 4마리다. 소 9마리가 다 들어가면 5번 칸만 비어 있다.