Число называется троичным, если оно содержит только цифры \(0\), \(1\) и \(2\). Например, следующие числа являются троичными: \(1022\), \(11\), \(21\), \(2002\).
Вам задано длинное троичное число \(x\). Первая (самая левая) цифра числа \(x\) гарантированно является \(2\), остальные цифры числа \(x\) могут быть \(0\), \(1\) или \(2\).
Определим троичную операцию XOR \(\odot\) над двумя троичными числами \(a\) и \(b\) (оба имеют длину \(n\)) как число \(c = a \odot b\) длины \(n\), где \(c_i = (a_i + b_i) \% 3\) (где \(\%\) — операция взятия по модулю). Другими словами, сложим соответствующие цифры и возьмем остатки от сумм при делении на \(3\). Например, \(10222 \odot 11021 = 21210\).
Ваша задача — найти такие троичные числа \(a\) и \(b\) (оба длины \(n\) и без лидирующих нулей), что \(a \odot b = x\) и \(max(a, b)\) — минимально возможный.
Вам нужно ответить на \(t\) независимых наборов входных данных.
Выходные данные
Для каждого набора входных данных выведите ответ на него — два троичных числа \(a\) и \(b\) (каждое длины \(n\) и без лидирующих нулей) таких, что \(a \odot b = x\) и \(max(a, b)\) — минимально возможное. Если есть несколько возможных ответов, вы можете вывести любой.