만만찮은 장치

카리브해 세인트바실 섬의 발굴 현장에서 낡은 장치 하나를 찾았다. 장치에는 퍼즐처럼 보이는 지시문이 함께 있었고, 현지 안내인 비베나스는 이 퍼즐을 풀면 장치가 해적 라이에르페스가 숨긴 보물의 위치를 알려 준다고 했다.

장치에는 $0$번부터 $L-1$번까지 번호가 붙은 $L$개의 칸으로 이루어진 테이프가 있다. 각 칸에는 색이 하나씩 칠해져 있고, 장치에 명령을 보내 그 색을 바꿀 수 있다. 색은 정수로 나타내며, 처음에는 모든 칸의 색이 같다.

지시문에는 장치가 길을 알려 주기 전에 수행해야 할 $N$개의 단계가 적혀 있다. 각 단계는 네 정수 $P$, $X$, $A$, $B$로 주어진다. 한 단계를 수행하려면 먼저 현재 색이 $P$인 칸의 개수를 센다. 이 개수를 $S$라고 할 때 다음 두 값을 계산한다.

$M_1 = (A + S^2) \bmod L$

$M_2 = (A + (S + B)^2) \bmod L$

마지막으로 닫힌 구간 $[\min(M_1, M_2), \max(M_1, M_2)]$에 속하는 모든 칸의 색을 $X$로 바꾼다.

$N$개의 단계를 모두 수행한 뒤, 테이프에 가장 많이 나타나는 색을 하나 고르고 그 색으로 칠해진 칸이 몇 개인지 구하라. 가장 많이 나타나는 색이 여럿이어도 그 개수는 하나로 정해진다.

첫 줄에 세 정수 $L$, $C$, $N$ ($1 \le L, C, N \le 10^5$)이 주어진다. 각각 테이프의 칸 수, 쓸 수 있는 색의 수, 지시문의 단계 수이다. 색은 $1$부터 $C$까지의 서로 다른 정수로 구분하고, 처음에는 모든 칸이 색 $1$이다.

다음 $N$개의 줄에는 각 단계가 네 정수 $P$, $X$, $A$, $B$ ($1 \le P, X \le C$, $0 \le A, B \le 10^8$)로 주어진다. $P$는 단계의 구간을 정할 때 개수를 세는 색, $X$는 단계를 수행한 뒤 구간 안의 칸이 가져야 할 색이고, $A$와 $B$는 위에서 설명한 대로 구간의 경계를 계산하는 데 쓴다. 단계는 주어진 순서대로 수행한다.

모든 단계를 순서대로 수행한 뒤 테이프에 가장 많이 나타나는 색을 하나 고르고, 그 색으로 칠해진 칸의 개수를 한 줄에 출력한다.