이 문제는 출력 전용 문제입니다. 즉, 테스트 케이스를 직접 다운로드하여 자신의 컴퓨터에서 답을 계산한 뒤, 프로그램을 제출하는 대신 텍스트 파일 형태로 답안을 제출해야 합니다.

Busy Beaver는 마감 기한이 몇 시간 남지 않은 수학 숙제를 시작했습니다(절대 이렇게 하지 마세요!). 숙제에는 총 $100$개의 문제가 있는데, Busy Beaver는 대회가 끝나기 전까지 이 중 몇 문제를 풀 수 있을까요?

각 문제는 연립 방정식 세트로 구성되어 있습니다(방정식의 형태에 대한 자세한 내용은 입력 형식을 참조하세요). 목표는 가능한 한 많은 방정식 세트에 대해 양의 정수 해를 찾는 것입니다. 각 세트는 $1$점이며, 총 $100$점 만점입니다.

입력

이 링크를 통해 테스트 데이터를 다운로드하세요.

각 방정식 세트는 첫 줄에 두 개의 숫자로 시작합니다. 방정식에 포함된 변수의 개수 $N$(알파벳 순서대로 앞의 $N$개 문자가 사용됨)과 방정식의 개수 $K$입니다. 그 뒤를 이어 각 방정식이 한 줄씩 총 $K$줄 주어집니다.

방정식 좌변의 각 항은 [양의 정수 계수, 최대 1000][최대 6개의 변수 리스트] 형식으로 간단하게 표현됩니다. 좌변은 항상 최대 $20$개의 이러한 항들의 합으로 구성되며(더하기 기호로 구분됨: 음수 계수를 가진 항은 없음), 우변은 항상 양의 정수입니다. 지수는 사용되지 않습니다. 예를 들어 $a^2bc$는 aabc 또는 caab와 같이 표기될 수 있습니다.

모든 방정식 세트는 모든 변수가 $10^{12}$를 넘지 않는 해를 가집니다. 방정식은 단순한 무작위 방식으로 생성되었으며, 특정 알고리즘에서 최악의 성능을 유도하도록 설계되지 않았습니다.

출력

첫 줄에는 해결한 방정식의 개수인 양의 정수 $A$ ($1 \le A \le 100$)를 출력합니다.

그다음 $A$줄에 걸쳐, 해결한 세트의 번호($1$부터 $100$까지)를 먼저 출력하고, 이어서 해당 세트의 변수 값들을 알파벳 순서대로 공백으로 구분하여 출력합니다.

예를 들어, $5$번 방정식 세트를 풀었을 때 $a = 1234$, $b = 5678$이었고, $10$번 방정식 세트를 풀었을 때 $a = 123$, $b = 456$, $c = 789$였다면, 출력 파일은 다음과 같을 수 있습니다.

2
5 1234 5678
10 123 456 789

각 방정식 세트는 번호로 최대 한 번만 나열될 수 있습니다. $A$개의 솔루션은 특정 순서로 출력할 필요가 없습니다(예: $10$번 세트의 해를 $5$번 세트의 해보다 먼저 출력해도 됩니다). 해가 여러 개인 경우, 모든 변수가 $10^{18}$ 이하인 해라면 무엇이든 출력해도 됩니다(위에서 언급했듯이 모든 세트는 모든 변수가 $10^{12}$ 이하인 해를 가집니다).

채점

출력 형식이 잘못되었거나, 제출한 방정식 세트의 해 중 하나라도 틀린 경우 점수는 $0$점이 됩니다. 그렇지 않은 경우 $A$점을 받게 됩니다.

알고리즘 설계를 돕기 위해 아래에 $100$개의 방정식 세트에 대한 정보를 제공합니다. 여기서 $M$은 해당 세트가 모든 변수가 $M$ 이하인 해를 가짐을 의미합니다.

• 1-2번: $N=1, K=1, M=10$
• 3-7번: $N=1, K=1, M=10^{12}$
• 8-9번: $N=2, K=2, M=10^{3}$
• 10-12번: $N=2, K=2, M=10^{6}$
• 13-20번: $N=2, K=2, M=10^{12}$
• 21-24번: $N=3, K=3, M=10^{3}$
• 25-33번: $N=3, K=3, M=10^{6}$
• 34-40번: $N=3, K=3, M=10^{12}$
• 41-57번: $N=3, K=2, M=10^{7}$
• 58-60번: $N=2, K=1, M=10^{7}$
• 61-70번: $N=2, K=1, M=10^{9}$
• 71-83번: $N=2, K=1, M=10^{10}$
• 84-92번: $N=2, K=1, M=10^{11}$
• 93-100번: $N=2, K=1, M=10^{12}$