34181번 - 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ドル$일이기 때문이다.