크롭 트라이앵글

몇몇 장난꾸러기들이 Discovery Channel을 너무 많이 본 나머지, 이제 밤중에 미스터리 서클 삼각형을 만들고 싶어 한다. 이들은 위에서 보면 일정한 간격의 격자처럼 보이는 넓은 농작물 밭 안에 그것을 만들고 싶어 한다. 밭에는 나무가 몇 그루 심어져 있다. 각 나무는 두 격자선의 교차점(격자점)에 놓여 있다. 장난꾸러기들은 미스터리 서클 삼각형의 꼭짓점이 이 나무들에 위치하기를 원한다. 또한 미스터리 서클 삼각형을 더 흥미롭게 만들기 위해, 그 삼각형의 중심 역시 어떤 격자점에 위치하기를 원한다. 삼각형의 꼭짓점이 ($x_{1}$, $y_{1}$), ($x_{2}$, $y_{2}$), ($x_{3}$, $y_{3}$)라면, 이 삼각형의 중심 좌표는 (($x_{1}$ + $x_{2}$ + $x_{3}$) / 3, ($y_{1}$ + $y_{2}$ + $y_{3}$) / 3)임을 상기하라.

격자에 있는 모든 나무의 위치를 나타내는 정수 좌표를 가진 점들의 집합이 주어진다. 이 점들의 집합에서 서로 다른 꼭짓점을 사용해 만들 수 있으며 중심 역시 격자점인(즉, 중심의 좌표가 정수인) 삼각형의 개수를 계산해야 한다.

삼각형의 넓이가 0이더라도 유효한 삼각형으로 간주한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ N ≤ 10, 0 ≤ A, B, C, D, $x_{0}$, $y_{0}$≤ $10^{9}$, 1 ≤ M ≤ $10^{9}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

3 ≤ n ≤ 100.

큰 데이터 세트 (테스트 세트 2 - 비공개)

3 ≤ n ≤ 100000.

입력의 첫 번째 줄에는 케이스의 수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정확히 하나의 공백으로 구분된 정수 n, A, B, C, D, $x_{0}$, $y_{0}$, M을 포함하는 한 줄로 이루어진다. n은 입력 집합에 있는 나무의 수이다. 수 n, A, B, C, D, $x_{0}$, $y_{0}$, M을 사용하면 다음 의사 코드가 입력 집합에 있는 나무들의 좌표를 출력한다. mod는 나머지 연산을 나타낸다.

매개변수는 입력 나무 집합에 중복이 없도록 선택된다.

`

X = x_{0}, Y = y_{0}
print X, Y
for i = 1 to n-1
  X = (A * X + B) mod M
  Y = (C * Y + D) mod M
  print X, Y

`

각 테스트 케이스마다 "Case #X: "을 포함하는 한 줄을 출력한다. 여기서 X는 1부터 시작하는 테스트 케이스 번호이다. 그 뒤에 3개의 서로 다른 나무에 위치하며 중심이 격자점인 삼각형의 개수를 나타내는 정수를 출력한다.

첫 번째 테스트 케이스에서 생성된 입력 집합의 4그루 나무는 (0, 1), (7, 3), (17, 5), (17, 7)이다.