선호하는 방

새로운 기숙사는 N개의 큰 방 (2 <= N <= 3,000,000)로 이루어진 원형으로, 방은 0부터 N-1까지 번호가 매겨져 있으며, 방 N-1은 방 0과 인접해 있습니다.

하루가 끝나면 학생들은 천천히 기숙사로 돌아옵니다. 각 학생들은 차지하고 싶은 선호하는 방이 있습니다. 그러나 선호하는 방이 이미 다른 학생에 의해 점유되어 있다면, 그녀는 그 방으로부터 순차적으로 스캔을 시작하여 최초의 빈 방을 찾아 그 방을 차지합니다. 만약 그녀가 N-1번 방을 넘어가면, 그녀는 0번 방부터 스캔을 계속합니다.

각 학생의 선호 방이 주어진 대로, 모든 학생들이 기숙사로 돌아온 후에 남아있는 방 중 가장 작은 인덱스를 결정해 주세요. 이 질문에 대한 답은 학생들이 기숙사로 돌아오는 순서에 영향을 받지 않습니다.

거대한 양의 입력을 읽는 문제를 피하기 위해, 이 문제의 입력은 K줄 (1 <= K <= 10,000)인 간결한 형식으로 지정됩니다. 지정된 형식은 다음과 같습니다:

X Y A B

이들 줄 중 하나는 XY 학생들에 대한 선호 방을 지정합니다: X 학생들은 각각 방 f(1) .. f(Y)를 선호합니다. 여기서 f(i) = (Ai + B) mod N입니다. A와 B의 값은 0...1,000,000,000 범위내에 있습니다.

모든 문제에 대한 표준 메모리 제한 64MB를 잊지 마세요.

• 첫 번째 줄: 두 개의 공백으로 구분된 정수: N과 K입니다.
• 두 번째 줄..1+K 번째 줄 : 각 줄은 정수 X Y A B를 포함하고 있으며, 위에서 설명한 의미를 가집니다. 이들 라인으로 지정된 학생들의 총 수는 최대 N-1입니다. 학생들은 이들 라인 중 몇 개로 같은 방에 추가될 수 있습니다.

• 첫 번째 줄: 비어있는 방의 최소 인덱스입니다.