MatKor짱~ 하-이! 나니가스키? 장카설유 요리모 장파서유!

MatKor에서는 장카설유보다 장파서유가 인기가 많다. 각각 장현우(changhw), 파니(pani), 서준이(osjoon), 유틸(utilforever)이다.

그러나 장파서유 중 서를 담당하는 서준이는 그룹 여자친구의 팬이다. 이번 학기 MatKor에 가입한 서준이의 목표는 MatKor 부원 모두를 여자친구의 팬으로 만드는 것이다. 서준이는 MatKor 부원이 많이 모이는 세미나를 틈타 목표를 이루려고 한다.

MatKor에는 총 $N\times M$명의 부원이 있고, $T$번의 세미나를 진행한다. 세미나를 들을 때 부원들은 $N\times M$ 모양 격자의 $x$, $y$ 좌표가 정수인 각 격자점에 한 명씩 배치되며, 각 부원의 $z$ 좌표는 \left\[ -1,1 \right] 범위의 실수에서 정해진 규칙에 따라 정해진다. 이때, $x$, $y$ 좌표가 $\left( i,j \right)$에 배치된 부원을 편의상 $\left( i,j \right)$번 부원이라고 부른다.

이제 $\left( i,j \right)$번 부원이 $t$번째 세미나에서의 $z$좌표를 결정하기 위해 먼저 아래와 같은 삼각파 꼴의 식을 정의한다. \[f\left( x \right) =\left\lvert 4x-2 \right\rvert -1\]

즉, x\in\left\[ 0,1 \right)범위에서, $x=\frac{1}{2}$를 기준으로 $f\left( x \right)$가 $1$에서 $-1$로 선형으로 감소하다가 다시 $1$까지 선형으로 증가하는 함수를 정의한다.

이제 각 부원별로 각속도 $\omega$와 위상 $\phi$를 정의한다. $\left( i,j \right)$번 부원의 각속도를 $\omega\_{i,j}$, 위상을 $\phi\_{i,j}$라 정의할 때, $t$번째 세미나에서의 $z$ 좌표는 f\left( \left\\{ \frac{\omega\_{i,j}t+\phi\_{i,j}}{T} \right\\} \right)이다. 여기서 \left\\{ x \right\\}는 소수 부분으로, \left\\{ x \right\\} :=x-\left\lfloor x \right\rfloor으로 정의된다. 즉, $\left( i,j \right)$번 부원의 $t$번째 세미나에서의 좌표는 \left( i,j,f\left( \left\\{ \frac{\omega\_{i,j}t+\phi\_{i,j}}{T} \right\\} \right) \right)이다.

이제 서준이는 $T$번의 세미나에서 각각 최소 몇 명의 부원을 여자친구의 팬으로 만들어야 모든 부원이 여자친구의 팬으로 만들어 서준이의 목표를 달성할 수 있을지 궁금하다. 임의의 두 부원에 대해, 한 명이 여자친구의 팬이고 두 부원의 유클리드 거리가 $\sqrt{2}$ 미만이면 다른 한 명도 여자친구의 팬으로 만들 수 있다. 이 과정은 연쇄적으로 일어난다.

각 세미나에 대해 서준이의 목표를 달성하기 위해 최소 몇 명의 부원을 직접 여자친구의 팬으로 만들어야 하는지 구해보자. 단, 각 세미나에 대해 서로 영향받지 않으며, 각 세미나가 시작하기 전 모든 부원이 여자친구의 팬이 아니도록 초기화된다. 즉, 각각에 대해 독립적인 상황이라 생각해 답을 구한다.

첫 번째 줄에 정수 $N,M(1\leq N,M\leq 100)$과 세미나의 횟수 $T(1\leq T\leq 10^5)$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$줄에 걸쳐 $i$번째 줄에 $\omega\_{i,1},\omega\_{i,2},\cdots ,\omega\_{i,M}(1\leq\omega\_{i,j}\leq 10)$을 의미하는 정수들이 공백으로 구분되어 주어진다.

$N+2$번째 줄부터 $N$줄에 걸쳐 $i$번째 줄에 $\phi\_{i,1},\phi\_{i,2},\cdots ,\phi\_{i,M}(0\leq\phi\_{ij}\<T)$을 의미하는 정수들이 공백으로 구분되어 주어진다.

첫 번째 줄부터 $T$줄에 걸쳐 $i$번째 줄에 $i$번째 세미나에서 서준이가 목표를 달성하기 위해 최소 몇 명의 부원을 여자친구의 팬으로 만들어야 하는지 출력한다.

이 문제의 시간 제한이 $1.16$초인 이유는 여자친구의 데뷔일이 $1$월 $16$일이기 때문이다.