시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 (추가 시간 없음) 256 MB 64 3 3 5.000%

문제

팰린드롬이란 거꾸로 읽어도 제대로 읽는 것과 같은 수를 의미한다.

예를 들어, 10진법 수 0, 3, 77, 12321는 모두 팰린드롬이다. 다만, 10진법 수 10, 610는 팰린드롬이 아니다. 어떤 수가 팰린드롬인지 그 여부를 따질 때에는 Leading zeros를 생각하지 않기로 하자.

팰린드롬이 아닌 7진법 수 610를 보자. 이는 팰린드롬인 7진법 수 535, 33, 6의 합으로 표현할 수 있다.

이처럼 B진법의 N자리 수 K가 주어질 때, 이를 팰린드롬인 B진법 수 세 개의 합으로 표현하는 프로그램을 작성하시오.

입력

T개의 테스트 케이스가 입력으로 주어진다.

각 테스트 케이스마다 하나의 줄에 BK가 사이에 공백을 두고 주어진다.

출력

각 테스트 케이스마다 하나의 줄에 답을 출력한다.

만약, B진법 수 K를 팰린드롬인 B진법 수 세 개의 합으로 표현할 수 없다면, "-1"(따옴표 제외)를 출력한다.

만일 표현할 수 있다면, 그 세 개의 수를 사이에 공백을 두고 출력한다. 세 개의 수는 모두 음이 아닌 올바른 B진법 수여야 하며, Leading zero가 있어서는 안된다.

제한

모든 입력 데이터는 아래의 조건을 모두 만족한다.

  • 1 ≤ T ≤ 2.5 × 105
  • 5 ≤ B ≤ 62
  • K는 올바른 B진법 양수다. 즉, 각 자릿수는 0 이상 B 미만이며 Leading zero를 포함하지 않는다.
  • 모든 테스트 케이스의 N의 합은 106을 넘지 않는다.

예제 입력 1

1
7 610

예제 출력 1

535 33 6

예제 입력 2

4
10 1
10 11
10 111
10 1111

예제 출력 2

1 0 0
11 0 0
101 9 1
111 999 1

0도 팰린드롬임에 유의하라.

답을 출력할 때, 세 수를 크기 순으로 출력할 필요는 없다.

예제 입력 3

6
11 A
12 B
28 R
36 Z
37 a
62 z

예제 출력 3

9 1 0
9 2 0
9 9 9
Y 1 0
Z 1 0
Z G A

각 알파벳이 어떤 수를 의미하는지는 하단의 노트를 참고하라.

예제 입력 4

7
7 20010610
10 20010610
12 ABA0BAB
40 GYOJUN0610YOUN
40 HaHaHa
61 WhatAWonderfulDay
62 ZzzZzz000

예제 출력 4

11122111 5434345 121121
11122111 8758578 129921
A10101A A6996A 32223
G101011110101G X9d4XVaVX4d9X EJPS7887SPJE
H0110H ZWAWZ OOOO
W011010111010110W gn75piqccqip57ng ll4f5v010v5f4ll
Z1111111Z yV6666Vy TSsrsST

노트

충분히 큰 진법에 대하여, 아래의 숫자를 10진법의 수로 변환하면 다음과 같다:

  • 0 = 0(10)
  • 9 = 9(10)
  • A = 10(10)
  • Z = 35(10)
  • a = 36(10)
  • z = 61(10)

출처

  • 문제를 만든 사람: yclock

제출할 수 있는 언어

C++14, Java, Python 3, C11, PyPy3, C, C++, C++11, C++17, Java (OpenJDK), C++2a, Python 2, PyPy2, C (Clang), C++ (Clang), C++11 (Clang), C++14 (Clang), C11 (Clang), C++17 (Clang), C++2a (Clang)