프뤼프줌메

우리 주변에는 은행 계좌 번호, 도서 ISBN, 상품 바코드처럼 긴 숫자 식별자가 많다. 이런 식별자는 사람이 직접 적거나 입력하는 경우가 많아서, 실수를 막으려고 오류 검출 기능이 내장되어 있는 경우가 많다.

오류 검출은 보통 체크섬의 형태로 이루어진다. 예를 들어 ISBN-10 코드는 다음 체크섬을 가지는 10자리 숫자열 $a_1, a_2, \dots, a_{10}$이다.

$10 \times a_1 + 9 \times a_2 + 8 \times a_3 + \dots + 2 \times a_9 + 1 \times a_{10} \pmod{11}$

체크섬은 0부터 10 사이의 수이며, 올바른 도서 코드에서는 항상 0이다. 이 체크섬은 오류 검출을 위해 설계되었고 다음 두 성질을 가진다.

1. 한 자리 숫자만 바꾸고 나머지는 그대로 두면 체크섬이 달라진다.
2. 서로 다른 인접한 두 자리 숫자를 맞바꾸고 나머지는 그대로 두면 체크섬이 달라진다.

다만 체크섬은 11가지 값을 가질 수 있는 반면 각 자리 숫자는 10가지 값만 가지므로, 다소 과하다고 볼 수 있다.

우리는 다음과 같이 아름다운 체크섬을 정의한다. 식별자는 각 값이 0 이상 $m-1$ 이하인 정수 $n$개로 이루어진 수열 $a_1, a_2, \dots, a_n$이다. 체크섬 알고리즘은 두 행렬 $p_{ij}$ ($0 \le i, j \le m-1$)와 $q_{ki}$ ($1 \le k \le n$, $0 \le i \le m-1$)로 정해지며, 두 행렬의 모든 값은 0 이상 $m-1$ 이하이다. 체크섬은 다음 순서로 계산한다.

1. $s_0 = 0$으로 둔다.
2. $k$를 1부터 $n$까지 증가시키며 다음을 수행한다.
   1. $t_k = q_{k,a_k}$로 둔다.
   2. $s_k = p_{s_{k-1},t_k}$로 둔다.
3. $s_n$을 체크섬으로 반환한다.

즉, 행렬 $q$는 각 위치마다 수를 변환하고, 행렬 $p$는 변환된 수들을 결합하는 규칙을 정한다. 주어진 $n$과 $m$에 대해 두 행렬 $p$와 $q$가 임의의 수열 $a$마다 위의 두 성질을 만족하는 체크섬을 이루면, 이를 아름다운 체크섬이라고 한다. 즉 하나의 수를 바꾸면 체크섬이 바뀌어야 하고, 서로 다른 인접한 두 수($a_k \ne a_{k+1}$인 어떤 $k$가 존재한다)를 맞바꾸어도 체크섬이 바뀌어야 한다.

예를 들어 $p_{ij} = i + j \pmod{11}$, $q_{ki} = (11 - k) \times i \pmod{11}$로 정의한 ISBN-10 방식은 $n=10$, $m=11$일 때 아름다운 체크섬이다.

주어진 $n$과 $m$에 대해 아름다운 체크섬을 만들 수 있는지 구하시오.

아름다운 체크섬이 존재하면 첫 줄에 Ja를 출력한다. 존재하지 않으면 Nein을 출력한다.

Ja를 출력한 경우, 체크섬의 내용을 이어서 출력한다. 다음 $m$줄에는 행렬 $p$를 출력한다. 각 줄에는 $m$개의 정수를 공백으로 구분하여 쓴다. $i$번째 줄(0부터 시작)의 $j$번째(0부터 시작) 값이 $p_{ij}$이다. 그 다음 $n$줄에는 행렬 $q$를 출력한다. 각 줄에는 $m$개의 정수를 공백으로 구분하여 쓴다. $k$번째 줄(1부터 시작)의 $i$번째(0부터 시작) 값이 $q_{ki}$이다.

출력하는 모든 수는 0 이상 $m-1$ 이하여야 한다. 해가 여러 개이면 아무거나 출력해도 된다.