結果
| 問題 | No.3408 1215 Segments |
| コンテスト | |
| ユーザー |
 uwi
|
| 提出日時 | 2026-03-27 12:56:28 |
| 言語 | Java (openjdk 25.0.2) |
| 結果 |
AC
|
| 実行時間 | 88 ms / 2,500 ms |
| コード長 | 47,726 bytes |
| 記録 | |
| コンパイル時間 | 3,947 ms |
| コンパイル使用メモリ | 93,224 KB |
| 実行使用メモリ | 44,836 KB |
| 最終ジャッジ日時 | 2026-03-27 12:56:44 |
| 合計ジャッジ時間 | 10,471 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 46 |
ソースコード
package no3xxx;
import java.io.*;
import java.util.*;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;
// 1033
// 数は少ないが、全列挙が難しい？
public class N3408_5 {
InputStream is;
FastWriter out;
String INPUT = "";
final int[] ds = {
0, 0, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 8, 9, 9
};
long trial(char[] s)
{
int n = s.length;
long min = Long.MAX_VALUE;
for(String v : all){
if(v.length() > n)continue;
int[] w = new int[n];
for(int i = 0;i < v.length();i++){
w[i] = Integer.parseInt("" + v.charAt(i), 16);
if(w[i] >= 12){
w[i]++;
}
}
for(int i = v.length();i < n;i++){
w[i] = 12;
}
int[] f = new int[10];
for(int i = 0;i < n;i++){
f[ds[w[i]]]++;
}
char[] t = notLessThan(f, s);
if(t != null){
long vv = Long.parseLong(new String(t));
min = Math.min(min, vv);
}
}
return min;
}
char[] notLessThan(int[] f, char[] s)
{
int n = s.length;
char[] t = new char[n];
for(int i = 0;i < n;i++){
if(f[s[i]-'0'] > 0){
f[s[i]-'0']--;
t[i] = s[i];
}else {
for (int j = i; j >= 0; j--) {
if(j<i)f[s[j]-'0']++;
for (int k = s[j] - '0' + 1; k < 10; k++) {
if (f[k] > 0) {
f[k]--;
t[j] = (char)('0'+k);
int m = j + 1;
for (int l = 0; l < 10; l++) {
while (f[l] > 0) {
f[l]--;
t[m++] = (char)('0'+l);
}
}
assert m == n;
return t;
}
}
}
return null;
}
}
return s;
}
public void solve()
{
char[] s = ns().toCharArray();
long v = trial(s);
if(v == Long.MAX_VALUE){
char[] t = new char[s.length+1];
Arrays.fill(t, '0');
t[0] = '1';
v = trial(t);
}
out.println(v);
// 0
// 1 2
// 3
// 4 5
// 6
}
public static boolean incAscending(int[] a, int base, boolean strict)
{
int n = a.length;
for(int i = n-1;i >= 0;i--){
if(++a[i] + (strict ? n-1-i : 0) < base){
for(int j = i+1;j < n;j++)a[j] = a[j-1] + (strict ? 1 : 0);
return true;
}
}
return false;
}
public static boolean inc(int[] a, int base)
{
int n = a.length;
int i;
for(i = n - 1;i >= 0 && a[i] == base - 1;i--);
if(i == -1)return false;
a[i]++;
Arrays.fill(a, i + 1, n, 0);
return true;
}
String[] all = {
"",
"0000113344446677dd",
"0000113344446678cdd",
"000011334444679cddd",
"000013344445666788d",
"00001334444566789dd",
"0000133444456799ddd",
"0000134444666788d",
"0000134444666888cd",
"000013444466789dd",
"000013444466889cdd",
"00001344446799ddd",
"00001344446899cddd",
"0000134444999cdddd",
"000034444566668888",
"00003444456668889d",
"0000344445668899dd",
"000034444568999ddd",
"00003444459999dddd",
"000044444666688889b",
"00004444466688899bd",
"0000444446688999bdd",
"000044444689999bddd",
"00004444499999bdddd",
"0000444466668888",
"000044446668889d",
"00004444668899dd",
"0000444468999ddd",
"000044449999dddd",
"000111333444cccddd",
"0001123334444677cdd",
"0001133334445567cdd",
"00011333444456677bd",
"0001133344446677acd",
"00011333444567cdd",
"00011333444568ccdd",
"0001133344459ccddd",
"000113344446677bd",
"000113344446678bcd",
"000113344446688bccd",
"00011334444679bcdd",
"00011334444689bccdd",
"0001133444499bccddd",
"000113344467cdd",
"000113344468ccdd",
"00011334449ccddd",
"000123334444566778d",
"00012333444456779dd",
"0001233444466778d",
"0001233444466788cd",
"0001233444466888ccd",
"000123344446779dd",
"000123344446789cdd",
"000123344446889ccdd",
"00012334444799cddd",
"00012334444899ccddd",
"000133334445556678d",
"00013333444555679dd",
"000133344445666778a",
"00013334444566779ad",
"0001333444556678d",
"0001333444556688cd",
"000133344455679dd",
"000133344455689cdd",
"00013334445599cddd",
"00013344445666788b",
"00013344445666888bc",
"0001334444566789bd",
"0001334444566889bcd",
"000133444456799bdd",
"000133444456899bcdd",
"00013344445999bcddd",
"0001334444666778a",
"0001334444666788ac",
"0001334444666888acc",
"000133444466779ad",
"000133444466789acd",
"000133444466889accd",
"00013344446799acdd",
"00013344446899accdd",
"0001334444999accddd",
"00013344456678d",
"00013344456688cd",
"0001334445679dd",
"0001334445689cdd",
"000133444599cddd",
"00013444446667889bb",
"0001344444667899bbd",
"000134444467999bbdd",
"000134444666788b",
"000134444666888bc",
"00013444466789bd",
"00013444466889bcd",
"0001344446799bdd",
"0001344446899bcdd",
"000134444999bcddd",
"000134446678d",
"000134446688cd",
"00013444679dd",
"00013444689cdd",
"0001344499cddd",
"000233444456667888",
"000233444456668888c",
"00023344445667889d",
"00023344445668889cd",
"0002334444567899dd",
"0002334444568899cdd",
"000233444457999ddd",
"000233444458999cddd",
"000234444466678889b",
"00023444446678899bd",
"0002344444678999bdd",
"000234444479999bddd",
"0002344446667888",
"0002344446668888c",
"000234444667889d",
"000234444668889cd",
"00023444467899dd",
"00023444468899cdd",
"0002344447999ddd",
"0002344448999cddd",
"000333444555666888",
"00033344455566889d",
"0003334445556899dd",
"000333444555999ddd",
"000334444556668889b",
"00033444455668899bd",
"0003344445568999bdd",
"000334444559999bddd",
"00033444456667889a",
"00033444456668889ac",
"0003344445667899ad",
"0003344445668899acd",
"000334444567999add",
"000334444568999acdd",
"00033444459999acddd",
"0003344455666888",
"000334445566889d",
"00033444556899dd",
"0003344455999ddd",
"00034444466678899ab",
"0003444446678999abd",
"000344444679999abdd",
"0003444456668889b",
"000344445668899bd",
"00034444568999bdd",
"0003444459999bddd",
"000344446667889a",
"000344446668889ac",
"00034444667899ad",
"00034444668899acd",
"0003444467999add",
"0003444468999acdd",
"000344449999acddd",
"00034445666888",
"0003444566889d",
"000344456899dd",
"00034445999ddd",
"0004444466688899bb",
"000444446688999bbd",
"00044444689999bbdd",
"0004444499999bbddd",
"00044446668889b",
"0004444668899bd",
"000444468999bdd",
"00044449999bddd",
"000444666888",
"00044466889d",
"0004446899dd",
"000444999ddd",
"0011133334445bcccdd",
"001113333444accccdd",
"00111333444467bbccd",
"00111333444bcccdd",
"00112333344457ccdd",
"00112333344458cccdd",
"001123334444677bcd",
"001123334444678bccd",
"00112333444479bccdd",
"001123334447ccdd",
"001123334448cccdd",
"00113333344555ccdd",
"001133334445567bcd",
"001133334445568bccd",
"00113333444559bccdd",
"00113333444567accd",
"00113333444568acccd",
"0011333344459acccdd",
"001133334455ccdd",
"0011333444456677bb",
"0011333444456678bbc",
"001133344445679bbcd",
"001133344446677abc",
"001133344446678abcc",
"00113334444679abccd",
"0011333444567bcd",
"0011333444568bccd",
"001133344459bccdd",
"001133344467accd",
"001133344468acccd",
"00113334449acccdd",
"0011333445ccdd",
"0011334444466779bbb",
"00113344446677bb",
"00113344446678bbc",
"00113344446688bbcc",
"0011334444679bbcd",
"0011334444689bbccd",
"001133444499bbccdd",
"00113344467bcd",
"00113344468bccd",
"0011334449bccdd",
"00113344ccdd",
"001223333444456777d",
"0012233344446777d",
"0012233344446778cd",
"0012233344446788ccd",
"001223334444779cdd",
"001223334444789ccdd",
"001233333444555677d",
"001233334444566777a",
"0012333344455677d",
"0012333344455678cd",
"0012333344455688ccd",
"001233334445579cdd",
"001233334445589ccdd",
"00123334444566778b",
"00123334444566788bc",
"0012333444456779bd",
"0012333444456789bcd",
"001233344445799bcdd",
"0012333444466777a",
"0012333444466778ac",
"0012333444466788acc",
"001233344446779acd",
"001233344446789accd",
"00123334444799accdd",
"00123334445677d",
"00123334445678cd",
"00123334445688ccd",
"0012333444579cdd",
"0012333444589ccdd",
"00123344444667789bb",
"0012334444467799bbd",
"001233444466778b",
"001233444466788bc",
"001233444466888bcc",
"00123344446779bd",
"00123344446789bcd",
"00123344446889bccd",
"0012334444799bcdd",
"0012334444899bccdd",
"001233444677d",
"001233444678cd",
"001233444688ccd",
"00123344479cdd",
"00123344489ccdd",
"001333333445555567d",
"001333334445556677a",
"0013333344555567d",
"0013333344555568cd",
"001333334455559cdd",
"00133334445556678b",
"00133334445556688bc",
"0013333444555679bd",
"0013333444555689bcd",
"001333344455599bcdd",
"0013333444556677a",
"0013333444556678ac",
"0013333444556688acc",
"001333344455679acd",
"001333344455689accd",
"00133334445599accdd",
"00133334455567d",
"00133334455568cd",
"0013333445559cdd",
"00133344445566789bb",
"0013334444556799bbd",
"0013334444566779ab",
"0013334444566789abc",
"001333444456799abcd",
"001333444466779aac",
"001333444466789aacc",
"00133344446799aaccd",
"001333444556678b",
"001333444556688bc",
"00133344455679bd",
"00133344455689bcd",
"0013334445599bcdd",
"00133344456677a",
"00133344456678ac",
"00133344456688acc",
"0013334445679acd",
"0013334445689accd",
"001333444599accdd",
"001333445567d",
"001333445568cd",
"00133344559cdd",
"0013344444667799abb",
"001334444566789bb",
"001334444566889bbc",
"00133444456799bbd",
"00133444456899bbcd",
"0013344445999bbcdd",
"00133444466779ab",
"00133444466789abc",
"00133444466889abcc",
"0013344446799abcd",
"0013344446899abccd",
"001334444999abccdd",
"0013344456678b",
"0013344456688bc",
"001334445679bd",
"001334445689bcd",
"00133444599bcdd",
"001334446677a",
"001334446678ac",
"001334446688acc",
"00133444679acd",
"00133444689accd",
"0013344499accdd",
"0013344567d",
"0013344568cd",
"001334459cdd",
"001344444667899bbb",
"001344444668899bbbc",
"00134444467999bbbd",
"00134444468999bbbcd",
"0013444449999bbbcdd",
"0013444466789bb",
"0013444466889bbc",
"001344446799bbd",
"001344446899bbcd",
"00134444999bbcdd",
"00134446678b",
"00134446688bc",
"0013444679bd",
"0013444689bcd",
"001344499bcdd",
"00134467d",
"00134468cd",
"0013449cdd",
"002233344445667788",
"002233344445667888c",
"00223334444567789d",
"00223334444567889cd",
"0022333444457799dd",
"0022333444457899cdd",
"002233444446677889b",
"00223344444677899bd",
"0022334444477999bdd",
"0022334444667788",
"0022334444667888c",
"0022334444668888cc",
"002233444467789d",
"002233444467889cd",
"002233444468889ccd",
"00223344447799dd",
"00223344447899cdd",
"00223344448899ccdd",
"002333344455566788",
"002333344455566888c",
"00233334445556789d",
"00233334445556889cd",
"0023333444555799dd",
"0023333444555899cdd",
"002333444455667889b",
"00233344445567899bd",
"0023334444557999bdd",
"00233344445667789a",
"00233344445667889ac",
"0023334444567799ad",
"0023334444567899acd",
"002333444457999acdd",
"0023334445566788",
"0023334445566888c",
"002333444556789d",
"002333444556889cd",
"00233344455799dd",
"00233344455899cdd",
"00233444446677899ab",
"0023344444677999abd",
"0023344445667889b",
"0023344445668889bc",
"002334444567899bd",
"002334444568899bcd",
"00233444457999bdd",
"00233444458999bcdd",
"002334444667789a",
"002334444667889ac",
"002334444668889acc",
"00233444467799ad",
"00233444467899acd",
"00233444468899accd",
"0023344447999acdd",
"0023344448999accdd",
"00233444566788",
"00233444566888c",
"0023344456789d",
"0023344456889cd",
"002334445799dd",
"002334445899cdd",
"0023444446678899bb",
"0023444446688899bbc",
"002344444678999bbd",
"002344444688999bbcd",
"00234444479999bbdd",
"00234444489999bbcdd",
"00234444667889b",
"00234444668889bc",
"0023444467899bd",
"0023444468899bcd",
"002344447999bdd",
"002344448999bcdd",
"002344466788",
"002344466888c",
"00234446789d",
"00234446889cd",
"0023444799dd",
"0023444899cdd",
"003333344555556688",
"00333334455555689d",
"0033333445555599dd",
"003333444555566889b",
"00333344455556899bd",
"0033334445555999bdd",
"00333344455566789a",
"00333344455566889ac",
"0033334445556799ad",
"0033334445556899acd",
"003333444555999acdd",
"0033334455556688",
"003333445555689d",
"00333344555599dd",
"00333444455667899ab",
"0033344445567999abd",
"0033344445667799aa",
"0033344445667899aac",
"003334444567999aacd",
"0033344455566889b",
"003334445556899bd",
"00333444555999bdd",
"003334445566789a",
"003334445566889ac",
"00333444556799ad",
"00333444556899acd",
"0033344455999acdd",
"00333445556688",
"0033344555689d",
"003334455599dd",
"0033444446677999aab",
"0033444455668899bb",
"003344445568999bbd",
"00334444559999bbdd",
"003344445667899ab",
"003344445668899abc",
"00334444567999abd",
"00334444568999abcd",
"0033444459999abcdd",
"00334444667799aa",
"00334444667899aac",
"00334444668899aacc",
"0033444467999aacd",
"0033444468999aaccd",
"003344449999aaccdd",
"00334445566889b",
"0033444556899bd",
"003344455999bdd",
"0033444566789a",
"0033444566889ac",
"003344456799ad",
"003344456899acd",
"00334445999acdd",
"003344556688",
"00334455689d",
"0033445599dd",
"0034444456688999bbb",
"003444445689999bbbd",
"00344444599999bbbdd",
"003444446678999abb",
"003444446688999abbc",
"00344444679999abbd",
"00344444689999abbcd",
"0034444499999abbcdd",
"00344445668899bb",
"0034444568999bbd",
"003444459999bbdd",
"0034444667899ab",
"0034444668899abc",
"003444467999abd",
"003444468999abcd",
"00344449999abcdd",
"003444566889b",
"00344456899bd",
"0034445999bdd",
"00344466789a",
"00344466889ac",
"0034446799ad",
"0034446899acd",
"003444999acdd",
"0034456688",
"003445689d",
"00344599dd",
"00444446688999bbb",
"0044444689999bbbd",
"004444499999bbbdd",
"004444668899bb",
"00444468999bbd",
"0044449999bbdd",
"0044466889b",
"004446899bd",
"00444999bdd",
"00446688",
"0044689d",
"004499dd",
"011133334445bbcccd",
"01113333444abccccd",
"0111333444467bbbcc",
"0111333444468bbbccc",
"011133344449bbbcccd",
"0111333444bbcccd",
"011223333444477bccd",
"011233333444557bccd",
"01123333344457acccd",
"0112333344445677bbc",
"011233334444677abcc",
"0112333344457bccd",
"0112333344458bcccd",
"011233334447acccd",
"011233334448accccd",
"01123334444677bbc",
"01123334444678bbcc",
"01123334444688bbccc",
"0112333444479bbccd",
"0112333444489bbcccd",
"01123334447bccd",
"01123334448bcccd",
"011333333445555bccd",
"01133333344555acccd",
"0113333344455567bbc",
"011333334445567abcc",
"01133333444567aaccc",
"0113333344555bccd",
"011333334455acccd",
"01133334445567bbc",
"01133334445568bbcc",
"0113333444559bbccd",
"0113333444567abcc",
"0113333444568abccc",
"011333344459abcccd",
"011333344467aaccc",
"011333344468aacccc",
"01133334449aaccccd",
"01133334455bccd",
"0113333445acccd",
"01133344445679bbbc",
"01133344445689bbbcc",
"0113334444599bbbccd",
"0113334444679abbcc",
"0113334444689abbccc",
"011333444499abbcccd",
"011333444567bbc",
"011333444568bbcc",
"01133344459bbccd",
"01133344467abcc",
"01133344468abccc",
"0113334449abcccd",
"011333445bccd",
"01133344acccd",
"01133444446799bbbbc",
"011334444679bbbc",
"011334444689bbbcc",
"01133444499bbbccd",
"0113344467bbc",
"0113344468bbcc",
"011334449bbccd",
"0113344bccd",
"0122233334444777cd",
"0122233334444778ccd",
"0122333334445577cd",
"0122333334445578ccd",
"01223333444456777b",
"01223333444456778bc",
"0122333344445779bcd",
"0122333344446777ac",
"0122333344446778acc",
"012233334444779accd",
"01223333444577cd",
"01223333444578ccd",
"01223333444588cccd",
"01223334444467779bb",
"012233344446777b",
"012233344446778bc",
"012233344446788bcc",
"012233344446888bccc",
"01223334444779bcd",
"01223334444789bccd",
"01223334444889bcccd",
"012233344477cd",
"012233344478ccd",
"012233344488cccd",
"0123333334455557cd",
"0123333334455558ccd",
"01233333444555677b",
"01233333444555678bc",
"0123333344455579bcd",
"0123333344455677ac",
"0123333344455678acc",
"012333334445579accd",
"01233333445557cd",
"01233333445558ccd",
"01233334444556779bb",
"0123333444456779abc",
"012333344446779aacc",
"012333344455677b",
"012333344455678bc",
"012333344455688bcc",
"01233334445579bcd",
"01233334445589bccd",
"01233334445677ac",
"01233334445678acc",
"01233334445688accc",
"0123333444579accd",
"0123333444589acccd",
"012333344557cd",
"012333344558ccd",
"012333444456779bb",
"012333444456789bbc",
"012333444456889bbcc",
"01233344445799bbcd",
"01233344445899bbccd",
"01233344446779abc",
"01233344446789abcc",
"01233344446889abccc",
"0123334444799abccd",
"0123334444899abcccd",
"0123334445677b",
"0123334445678bc",
"0123334445688bcc",
"012333444579bcd",
"012333444589bccd",
"012333444677ac",
"012333444678acc",
"012333444688accc",
"01233344479accd",
"01233344489acccd",
"0123334457cd",
"0123334458ccd",
"012334444467799bbb",
"012334444467899bbbc",
"01233444447999bbbcd",
"0123344446779bb",
"0123344446789bbc",
"0123344446889bbcc",
"012334444799bbcd",
"012334444899bbccd",
"01233444677b",
"01233444678bc",
"01233444688bcc",
"0123344479bcd",
"0123344489bccd",
"01233447cd",
"01233448ccd",
"0133333334555555cd",
"01333333445555567b",
"01333333445555568bc",
"0133333344555559bcd",
"0133333344555567ac",
"0133333344555568acc",
"013333334455559accd",
"01333333455555cd",
"01333334445555679bb",
"0133333444555679abc",
"013333344455679aacc",
"013333344555567b",
"013333344555568bc",
"01333334455559bcd",
"01333334455567ac",
"01333334455568acc",
"0133333445559accd",
"013333345555cd",
"013333444555679bb",
"013333444555689bbc",
"01333344455599bbcd",
"01333344455679abc",
"01333344455689abcc",
"0133334445599abccd",
"0133334445679aacc",
"0133334445689aaccc",
"013333444599aacccd",
"0133334455567b",
"0133334455568bc",
"013333445559bcd",
"013333445567ac",
"013333445568acc",
"01333344559accd",
"0133334555cd",
"013334444556799bbb",
"013334444556899bbbc",
"01333444455999bbbcd",
"01333444456799abbc",
"01333444456899abbcc",
"0133344445999abbccd",
"0133344446799aabcc",
"0133344446899aabccc",
"013334444999aabcccd",
"0133344455679bb",
"0133344455689bbc",
"013334445599bbcd",
"013334445679abc",
"013334445689abcc",
"01333444599abccd",
"01333444679aacc",
"01333444689aaccc",
"0133344499aacccd",
"01333445567b",
"01333445568bc",
"0133344559bcd",
"0133344567ac",
"0133344568acc",
"013334459accd",
"01333455cd",
"013344444567999bbbb",
"01334444467999abbbc",
"0133444456799bbb",
"0133444456899bbbc",
"013344445999bbbcd",
"013344446799abbc",
"013344446899abbcc",
"01334444999abbccd",
"01334445679bb",
"01334445689bbc",
"0133444599bbcd",
"0133444679abc",
"0133444689abcc",
"013344499abccd",
"013344567b",
"013344568bc",
"01334459bcd",
"01334467ac",
"01334468acc",
"0133449accd",
"013345cd",
"0134444467999bbbb",
"0134444468999bbbbc",
"013444449999bbbbcd",
"01344446799bbb",
"01344446899bbbc",
"0134444999bbbcd",
"013444679bb",
"013444689bbc",
"01344499bbcd",
"0134467b",
"0134468bc",
"013449bcd",
"0134cd",
"022233334444567778",
"022233334444567788c",
"02223333444457779d",
"02223333444457789cd",
"022233344444677789b",
"02223334444477799bd",
"0222333444467778",
"0222333444467788c",
"0222333444467888cc",
"0222333444468888ccc",
"022233344447779d",
"022233344447789cd",
"022233344447889ccd",
"022233344448889cccd",
"022333334445556778",
"022333334445556788c",
"02233333444555779d",
"02233333444555789cd",
"022333344445567789b",
"02233334444557799bd",
"02233334444567779a",
"02233334444567789ac",
"0223333444457799acd",
"0223333444556778",
"0223333444556788c",
"0223333444556888cc",
"022333344455779d",
"022333344455789cd",
"022333344455889ccd",
"02233344444677799ab",
"0223334444567789b",
"0223334444567889bc",
"0223334444568889bcc",
"022333444457799bd",
"022333444457899bcd",
"022333444458899bccd",
"022333444467779a",
"022333444467789ac",
"022333444467889acc",
"022333444468889accc",
"02233344447799acd",
"02233344447899accd",
"02233344448899acccd",
"02233344456778",
"02233344456788c",
"02233344456888cc",
"0223334445779d",
"0223334445789cd",
"0223334445889ccd",
"0223344444677899bb",
"0223344444678899bbc",
"022334444477999bbd",
"022334444478999bbcd",
"02233444467789b",
"02233444467889bc",
"02233444468889bcc",
"0223344447799bd",
"0223344447899bcd",
"0223344448899bccd",
"022334446778",
"022334446788c",
"022334446888cc",
"02233444779d",
"02233444789cd",
"02233444889ccd",
"023333334455555678",
"023333334455555688c",
"02333333445555579d",
"02333333445555589cd",
"023333344455556789b",
"02333334445555799bd",
"02333334445556779a",
"02333334445556789ac",
"0233333444555799acd",
"0233333445555678",
"0233333445555688c",
"023333344555579d",
"023333344555589cd",
"02333344445567799ab",
"0233334444567799aac",
"0233334445556789b",
"0233334445556889bc",
"023333444555799bd",
"023333444555899bcd",
"023333444556779a",
"023333444556789ac",
"023333444556889acc",
"02333344455799acd",
"02333344455899accd",
"02333344555678",
"02333344555688c",
"0233334455579d",
"0233334455589cd",
"0233344445567899bb",
"0233344445568899bbc",
"023334444557999bbd",
"023334444558999bbcd",
"023334444567799ab",
"023334444567899abc",
"023334444568899abcc",
"02333444457999abcd",
"02333444458999abccd",
"02333444467799aac",
"02333444467899aacc",
"02333444468899aaccc",
"0233344447999aaccd",
"0233344448999aacccd",
"02333444556789b",
"02333444556889bc",
"0233344455799bd",
"0233344455899bcd",
"0233344456779a",
"0233344456789ac",
"0233344456889acc",
"023334445799acd",
"023334445899accd",
"023334455678",
"023334455688c",
"02333445579d",
"02333445589cd",
"0233444445678999bbb",
"023344444579999bbbd",
"023344444677999abb",
"023344444678999abbc",
"02334444479999abbcd",
"02334444567899bb",
"02334444568899bbc",
"0233444457999bbd",
"0233444458999bbcd",
"0233444467799ab",
"0233444467899abc",
"0233444468899abcc",
"023344447999abcd",
"023344448999abccd",
"023344456789b",
"023344456889bc",
"02334445799bd",
"02334445899bcd",
"02334446779a",
"02334446789ac",
"02334446889acc",
"0233444799acd",
"0233444899accd",
"0233445678",
"0233445688c",
"023344579d",
"023344589cd",
"02344444678999bbb",
"02344444688999bbbc",
"0234444479999bbbd",
"0234444489999bbbcd",
"023444467899bb",
"023444468899bbc",
"02344447999bbd",
"02344448999bbcd",
"0234446789b",
"0234446889bc",
"023444799bd",
"023444899bcd",
"02344678",
"02344688c",
"0234479d",
"0234489cd",
"033333334555555568",
"03333333455555559d",
"033333344555555689b",
"03333334455555599bd",
"03333334455555679a",
"03333334455555689ac",
"0333333445555599acd",
"0333333455555568",
"033333345555559d",
"03333344455556799ab",
"0333334445556799aac",
"0333334455555689b",
"033333445555599bd",
"033333445555679a",
"033333445555689ac",
"03333344555599acd",
"03333345555568",
"0333334555559d",
"0333344455556899bb",
"033334445555999bbd",
"033334445556799ab",
"033334445556899abc",
"03333444555999abcd",
"03333444556799aac",
"03333444556899aacc",
"0333344455999aaccd",
"03333445555689b",
"0333344555599bd",
"0333344555679a",
"0333344555689ac",
"033334455599acd",
"033334555568",
"03333455559d",
"0333444455568999bbb",
"033344445559999bbbd",
"033344445567999abb",
"033344445568999abbc",
"03334444559999abbcd",
"03334444567999aabc",
"03334444568999aabcc",
"0333444459999aabccd",
"0333444467999aaacc",
"0333444468999aaaccc",
"033344449999aaacccd",
"03334445556899bb",
"0333444555999bbd",
"0333444556799ab",
"0333444556899abc",
"033344455999abcd",
"033344456799aac",
"033344456899aacc",
"03334445999aaccd",
"033344555689b",
"03334455599bd",
"03334455679a",
"03334455689ac",
"0333445599acd",
"0333455568",
"033345559d",
"033444445679999abbb",
"03344444679999aabbc",
"03344445568999bbb",
"0334444559999bbbd",
"0334444567999abb",
"0334444568999abbc",
"033444459999abbcd",
"033444467999aabc",
"033444468999aabcc",
"03344449999aabccd",
"033444556899bb",
"03344455999bbd",
"03344456799ab",
"03344456899abc",
"0334445999abcd",
"0334446799aac",
"0334446899aacc",
"033444999aaccd",
"0334455689b",
"033445599bd",
"033445679a",
"033445689ac",
"03344599acd",
"03345568",
"0334559d",
"03444445689999bbbb",
"0344444599999bbbbd",
"0344444679999abbb",
"0344444689999abbbc",
"034444499999abbbcd",
"034444568999bbb",
"03444459999bbbd",
"03444467999abb",
"03444468999abbc",
"0344449999abbcd",
"0344456899bb",
"034445999bbd",
"034446799ab",
"034446899abc",
"03444999abcd",
"03445689b",
"0344599bd",
"0344679a",
"0344689ac",
"034499acd",
"034568",
"03459d",
"04444446899999bbbbb",
"0444444999999bbbbbd",
"044444689999bbbb",
"04444499999bbbbd",
"0444468999bbb",
"044449999bbbd",
"04446899bb",
"0444999bbd",
"044689b",
"04499bd",
"0468",
"049d",
"1112333344447bbbccc",
"1113333344455bbbccc",
"111333334445abbcccc",
"11133333444aabccccc",
"11133334445bbbccc",
"1113333444abbcccc",
"11133344449bbbbccc",
"111333444bbbccc",
"11223333444477bbcc",
"11223333444478bbccc",
"11233333444557bbcc",
"11233333444558bbccc",
"1123333344457abccc",
"1123333344458abcccc",
"112333334447aacccc",
"112333334448aaccccc",
"11233334444579bbbcc",
"1123333444479abbccc",
"112333344457bbcc",
"112333344458bbccc",
"11233334447abccc",
"11233334448abcccc",
"112333444479bbbcc",
"112333444489bbbccc",
"1123334447bbcc",
"1123334448bbccc",
"11333333445555bbcc",
"1133333344555abccc",
"113333334455aacccc",
"11333334445559bbbcc",
"1133333444559abbccc",
"113333344459aabcccc",
"11333334449aaaccccc",
"113333344555bbcc",
"11333334455abccc",
"1133333445aacccc",
"113333444559bbbcc",
"11333344459abbccc",
"1133334449aabcccc",
"1133334455bbcc",
"113333445abccc",
"11333344aacccc",
"113334444599bbbbcc",
"11333444499abbbccc",
"1133344459bbbcc",
"113334449abbccc",
"11333445bbcc",
"1133344abccc",
"113344444999bbbbbcc",
"1133444499bbbbcc",
"11334449bbbcc",
"113344bbcc",
"12223333344445777bc",
"1222333334444777acc",
"122233334444777bc",
"122233334444778bcc",
"122233334444788bccc",
"12233333344455577bc",
"1223333334445577acc",
"122333334445577bc",
"122333334445578bcc",
"122333334445588bccc",
"12233333444577acc",
"12233333444578accc",
"12233333444588acccc",
"122333344445779bbc",
"122333344445789bbcc",
"12233334444779abcc",
"12233334444789abccc",
"1223333444577bc",
"1223333444578bcc",
"1223333444588bccc",
"122333344477acc",
"122333344478accc",
"122333344488acccc",
"122333444447799bbbc",
"1223334444779bbc",
"1223334444789bbcc",
"1223334444889bbccc",
"12233344477bc",
"12233344478bcc",
"12233344488bccc",
"12333333344555557bc",
"1233333334455557acc",
"123333334455557bc",
"123333334455558bcc",
"12333333445557acc",
"12333333445558accc",
"123333344455579bbc",
"123333344455589bbcc",
"12333334445579abcc",
"12333334445589abccc",
"1233333444579aaccc",
"1233333444589aacccc",
"1233333445557bc",
"1233333445558bcc",
"123333344557acc",
"123333344558accc",
"123333444455799bbbc",
"12333344445799abbcc",
"1233334444799aabccc",
"1233334445579bbc",
"1233334445589bbcc",
"123333444579abcc",
"123333444589abccc",
"12333344479aaccc",
"12333344489aacccc",
"12333344557bc",
"12333344558bcc",
"1233334457acc",
"1233334458accc",
"1233344445799bbbc",
"1233344445899bbbcc",
"123334444799abbcc",
"123334444899abbccc",
"12333444579bbc",
"12333444589bbcc",
"1233344479abcc",
"1233344489abccc",
"123334457bc",
"123334458bcc",
"12333447acc",
"12333448accc",
"1233444447999bbbbc",
"1233444448999bbbbcc",
"12334444799bbbc",
"12334444899bbbcc",
"123344479bbc",
"123344489bbcc",
"1233447bc",
"1233448bcc",
"13333333345555555bc",
"1333333334555555acc",
"133333334555555bc",
"13333333455555acc",
"133333344555559bbc",
"13333334455559abcc",
"1333333445559aaccc",
"1333333455555bc",
"133333345555acc",
"133333444555599bbbc",
"13333344455599abbcc",
"1333334445599aabccc",
"133333444599aaacccc",
"1333334455559bbc",
"133333445559abcc",
"13333344559aaccc",
"13333345555bc",
"1333334555acc",
"1333344455599bbbc",
"133334445599abbcc",
"13333444599aabccc",
"1333344499aaacccc",
"13333445559bbc",
"1333344559abcc",
"133334459aaccc",
"133334555bc",
"13333455acc",
"1333444455999bbbbc",
"133344445999abbbcc",
"13334444999aabbccc",
"13334445599bbbc",
"1333444599abbcc",
"133344499aabccc",
"133344559bbc",
"13334459abcc",
"1333449aaccc",
"1333455bc",
"133345acc",
"1334444459999bbbbbc",
"133444449999abbbbcc",
"13344445999bbbbc",
"1334444999abbbcc",
"133444599bbbc",
"13344499abbcc",
"1334459bbc",
"133449abcc",
"13345bc",
"1334acc",
"13444449999bbbbbc",
"134444999bbbbc",
"1344499bbbc",
"13449bbc",
"134bc",
"222233333444457777",
"222233333444457778c",
"222233334444477779b",
"2222333344447777",
"2222333344447778c",
"2222333344447788cc",
"2222333344447888ccc",
"222333333444555777",
"222333333444555778c",
"222333334444557779b",
"22233333444457779ac",
"2223333344455777",
"2223333344455778c",
"2223333344455788cc",
"2223333344455888ccc",
"2223333444457779b",
"2223333444457789bc",
"2223333444457889bcc",
"222333344447779ac",
"222333344447789acc",
"222333344447889accc",
"22233334445777",
"22233334445778c",
"22233334445788cc",
"22233334445888ccc",
"2223334444477799bb",
"2223334444477899bbc",
"22233344447779b",
"22233344447789bc",
"22233344447889bcc",
"22233344448889bccc",
"222333444777",
"222333444778c",
"222333444788cc",
"222333444888ccc",
"223333333445555577",
"223333333445555578c",
"223333334445555779b",
"22333333444555779ac",
"2233333344555577",
"2233333344555578c",
"2233333344555588cc",
"2233333444555779b",
"2233333444555789bc",
"2233333444555889bcc",
"223333344455779ac",
"223333344455789acc",
"223333344455889accc",
"22333334455577",
"22333334455578c",
"22333334455588cc",
"2233334444557799bb",
"2233334444557899bbc",
"223333444457799abc",
"223333444457899abcc",
"22333344447799aacc",
"22333344447899aaccc",
"22333344455779b",
"22333344455789bc",
"22333344455889bcc",
"2233334445779ac",
"2233334445789acc",
"2233334445889accc",
"223333445577",
"223333445578c",
"223333445588cc",
"2233344444577999bbb",
"223334444477999abbc",
"22333444457799bb",
"22333444457899bbc",
"22333444458899bbcc",
"2233344447799abc",
"2233344447899abcc",
"2233344448899abccc",
"223334445779b",
"223334445789bc",
"223334445889bcc",
"22333444779ac",
"22333444789acc",
"22333444889accc",
"2233344577",
"2233344578c",
"2233344588cc",
"22334444477999bbb",
"22334444478999bbbc",
"22334444488999bbbcc",
"223344447799bb",
"223344447899bbc",
"223344448899bbcc",
"2233444779b",
"2233444789bc",
"2233444889bcc",
"22334477",
"22334478c",
"22334488cc",
"233333333455555557",
"233333333455555558c",
"233333334455555579b",
"23333333445555579ac",
"2333333345555557",
"2333333345555558c",
"2333333445555579b",
"2333333445555589bc",
"233333344555579ac",
"233333344555589acc",
"23333334555557",
"23333334555558c",
"2333334445555799bb",
"2333334445555899bbc",
"233333444555799abc",
"233333444555899abcc",
"23333344455799aacc",
"23333344455899aaccc",
"23333344555579b",
"23333344555589bc",
"2333334455579ac",
"2333334455589acc",
"233333455557",
"233333455558c",
"2333344445557999bbb",
"233334444557999abbc",
"23333444457999aabcc",
"2333344447999aaaccc",
"23333444555799bb",
"23333444555899bbc",
"2333344455799abc",
"2333344455899abcc",
"233334445799aacc",
"233334445899aaccc",
"233334455579b",
"233334455589bc",
"23333445579ac",
"23333445589acc",
"2333345557",
"2333345558c",
"23334444557999bbb",
"23334444558999bbbc",
"2333444457999abbc",
"2333444458999abbcc",
"233344447999aabcc",
"233344448999aabccc",
"233344455799bb",
"233344455899bbc",
"23334445799abc",
"23334445899abcc",
"2333444799aacc",
"2333444899aaccc",
"2333445579b",
"2333445589bc",
"233344579ac",
"233344589acc",
"23334557",
"23334558c",
"23344444579999bbbb",
"23344444589999bbbbc",
"2334444479999abbbc",
"2334444489999abbbcc",
"233444457999bbb",
"233444458999bbbc",
"23344447999abbc",
"23344448999abbcc",
"2334445799bb",
"2334445899bbc",
"233444799abc",
"233444899abcc",
"23344579b",
"23344589bc",
"2334479ac",
"2334489acc",
"233457",
"233458c",
"23444444799999bbbbb",
"234444479999bbbb",
"234444489999bbbbc",
"2344447999bbb",
"2344448999bbbc",
"23444799bb",
"23444899bbc",
"234479b",
"234489bc",
"2347",
"2348c",
"333333333555555555",
"333333334555555559b",
"33333333455555559ac",
"3333333355555555",
"3333333455555559b",
"333333345555559ac",
"33333335555555",
"3333334455555599bb",
"333333445555599abc",
"33333344555599aacc",
"33333345555559b",
"3333334555559ac",
"333333555555",
"3333344455555999bbb",
"333334445555999abbc",
"33333444555999aabcc",
"3333344455999aaaccc",
"33333445555599bb",
"3333344555599abc",
"333334455599aacc",
"333334555559b",
"33333455559ac",
"3333355555",
"33334445555999bbb",
"3333444555999abbc",
"333344455999aabcc",
"33334445999aaaccc",
"333344555599bb",
"33334455599abc",
"3333445599aacc",
"3333455559b",
"333345559ac",
"33335555",
"33344445559999bbbb",
"3334444559999abbbc",
"333444459999aabbcc",
"33344449999aaabccc",
"333444555999bbb",
"33344455999abbc",
"3334445999aabcc",
"333444999aaaccc",
"3334455599bb",
"333445599abc",
"33344599aacc",
"33345559b",
"3334559ac",
"333555",
"33444445599999bbbbb",
"3344444599999abbbbc",
"334444499999aabbbcc",
"334444559999bbbb",
"33444459999abbbc",
"3344449999aabbcc",
"3344455999bbb",
"334445999abbc",
"33444999aabcc",
"33445599bb",
"3344599abc",
"334499aacc",
"334559b",
"33459ac",
"3355",
"344444599999bbbbb",
"34444499999abbbbc",
"3444459999bbbb",
"344449999abbbc",
"34445999bbb",
"3444999abbc",
"344599bb",
"34499abc",
"3459b",
"349ac",
"35",
"444444999999bbbbbb",
"4444499999bbbbb",
"44449999bbbb",
"444999bbb",
"4499bb",
"49b"
};
public static void main(String[] args) {
new N3408_5().run();
}
public void run()
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new FastWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
// Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
// @Override
// public void run() {
// long s = System.currentTimeMillis();
// solve();
// out.flush();
// if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
// }
// };
// t.start();
// t.join();
}
private boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private final byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
// private boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[][] nmi(int n, int m)
{
int[][] map = new int[n][];
for(int i = 0;i < n;i++)map[i] = na(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private long[] nal(int n)
{
long[] a = new long[n];
for(int i = 0;i < n;i++)a[i] = nl();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
public static class FastWriter
{
private static final int BUF_SIZE = 1<<13;
private final byte[] buf = new byte[BUF_SIZE];
private final OutputStream out;
private int ptr = 0;
private FastWriter(){out = null;}
public FastWriter(OutputStream os)
{
this.out = os;
}
public FastWriter(String path)
{
try {
this.out = new FileOutputStream(path);
} catch (FileNotFoundException e) {
throw new RuntimeException("FastWriter");
}
}
public FastWriter write(byte b)
{
buf[ptr++] = b;
if(ptr == BUF_SIZE)innerflush();
return this;
}
public FastWriter write(char c)
{
return write((byte)c);
}
public FastWriter write(char[] s)
{
for(char c : s){
buf[ptr++] = (byte)c;
if(ptr == BUF_SIZE)innerflush();
}
return this;
}
public FastWriter write(String s)
{
s.chars().forEach(c -> {
buf[ptr++] = (byte)c;
if(ptr == BUF_SIZE)innerflush();
});
return this;
}
private static int countDigits(int l) {
if (l >= 1000000000) return 10;
if (l >= 100000000) return 9;
if (l >= 10000000) return 8;
if (l >= 1000000) return 7;
if (l >= 100000) return 6;
if (l >= 10000) return 5;
if (l >= 1000) return 4;
if (l >= 100) return 3;
if (l >= 10) return 2;
return 1;
}
public FastWriter write(int x)
{
if(x == Integer.MIN_VALUE){
return write((long)x);
}
if(ptr + 12 >= BUF_SIZE)innerflush();
if(x < 0){
write((byte)'-');
x = -x;
}
int d = countDigits(x);
for(int i = ptr + d - 1;i >= ptr;i--){
buf[i] = (byte)('0'+x%10);
x /= 10;
}
ptr += d;
return this;
}
private static int countDigits(long l) {
if (l >= 1000000000000000000L) return 19;
if (l >= 100000000000000000L) return 18;
if (l >= 10000000000000000L) return 17;
if (l >= 1000000000000000L) return 16;
if (l >= 100000000000000L) return 15;
if (l >= 10000000000000L) return 14;
if (l >= 1000000000000L) return 13;
if (l >= 100000000000L) return 12;
if (l >= 10000000000L) return 11;
if (l >= 1000000000L) return 10;
if (l >= 100000000L) return 9;
if (l >= 10000000L) return 8;
if (l >= 1000000L) return 7;
if (l >= 100000L) return 6;
if (l >= 10000L) return 5;
if (l >= 1000L) return 4;
if (l >= 100L) return 3;
if (l >= 10L) return 2;
return 1;
}
public FastWriter write(long x)
{
if(x == Long.MIN_VALUE){
return write("" + x);
}
if(ptr + 21 >= BUF_SIZE)innerflush();
if(x < 0){
write((byte)'-');
x = -x;
}
int d = countDigits(x);
for(int i = ptr + d - 1;i >= ptr;i--){
buf[i] = (byte)('0'+x%10);
x /= 10;
}
ptr += d;
return this;
}
public FastWriter write(double x, int precision)
{
if(x < 0){
write('-');
x = -x;
}
x += Math.pow(10, -precision)/2;
// if(x < 0){ x = 0; }
write((long)x).write(".");
x -= (long)x;
for(int i = 0;i < precision;i++){
x *= 10;
write((char)('0'+(int)x));
x -= (int)x;
}
return this;
}
public FastWriter writeln(char c){ return write(c).writeln(); }
public FastWriter writeln(int x){ return write(x).writeln(); }
public FastWriter writeln(long x){ return write(x).writeln(); }
public FastWriter writeln(double x, int precision){ return write(x, precision).writeln(); }
public FastWriter write(int... xs)
{
boolean first = true;
for(int x : xs) {
if (!first) write(' ');
first = false;
write(x);
}
return this;
}
public FastWriter write(long... xs)
{
boolean first = true;
for(long x : xs) {
if (!first) write(' ');
first = false;
write(x);
}
return this;
}
public FastWriter write(IntUnaryOperator f, int... xs)
{
boolean first = true;
for(int x : xs) {
if (!first) write(' ');
first = false;
write(f.applyAsInt(x));
}
return this;
}
public FastWriter write(LongUnaryOperator f, long... xs)
{
boolean first = true;
for(long x : xs) {
if (!first) write(' ');
first = false;
write(f.applyAsLong(x));
}
return this;
}
public FastWriter writeln()
{
return write((byte)'\n');
}
public FastWriter writeln(int... xs) { return write(xs).writeln(); }
public FastWriter writeln(long... xs) { return write(xs).writeln(); }
public FastWriter writeln(IntUnaryOperator f, int... xs) { return write(f, xs).writeln(); }
public FastWriter writeln(LongUnaryOperator f, long... xs) { return write(f, xs).writeln(); }
public FastWriter writeln(char[] line) { return write(line).writeln(); }
public FastWriter writeln(char[]... map) { for(char[] line : map)write(line).writeln();return this; }
public FastWriter writeln(String s) { return write(s).writeln(); }
private void innerflush()
{
try {
out.write(buf, 0, ptr);
ptr = 0;
} catch (IOException e) {
throw new RuntimeException("innerflush");
}
}
public void flush()
{
innerflush();
try {
out.flush();
} catch (IOException e) {
throw new RuntimeException("flush");
}
}
public FastWriter print(byte b) { return write(b); }
public FastWriter print(char c) { return write(c); }
public FastWriter print(char[] s) { return write(s); }
public FastWriter print(String s) { return write(s); }
public FastWriter print(int x) { return write(x); }
public FastWriter print(long x) { return write(x); }
public FastWriter print(double x, int precision) { return write(x, precision); }
public FastWriter println(char c){ return writeln(c); }
public FastWriter println(int x){ return writeln(x); }
public FastWriter println(long x){ return writeln(x); }
public FastWriter println(double x, int precision){ return writeln(x, precision); }
public FastWriter print(int... xs) { return write(xs); }
public FastWriter print(long... xs) { return write(xs); }
public FastWriter print(IntUnaryOperator f, int... xs) { return write(f, xs); }
public FastWriter print(LongUnaryOperator f, long... xs) { return write(f, xs); }
public FastWriter println(int... xs) { return writeln(xs); }
public FastWriter println(long... xs) { return writeln(xs); }
public FastWriter println(IntUnaryOperator f, int... xs) { return writeln(f, xs); }
public FastWriter println(LongUnaryOperator f, long... xs) { return writeln(f, xs); }
public FastWriter println(char[] line) { return writeln(line); }
public FastWriter println(char[]... map) { return writeln(map); }
public FastWriter println(String s) { return writeln(s); }
public FastWriter println() { return writeln(); }
}
public static void trnz(int... o)
{
for(int i = 0;i < o.length;i++)if(o[i] != 0)System.out.print(i+":"+o[i]+" ");
System.out.println();
}
// print ids which are 1
public static void trt(long... o)
{
Queue<Integer> stands = new ArrayDeque<>();
for(int i = 0;i < o.length;i++){
for(long x = o[i];x != 0;x &= x-1)stands.add(i<<6|Long.numberOfTrailingZeros(x));
}
System.out.println(stands);
}
public static void tf(boolean... r)
{
for(boolean x : r)System.out.print(x?'#':'.');
System.out.println();
}
public static void tf(boolean[]... b)
{
for(boolean[] r : b) {
for(boolean x : r)System.out.print(x?'#':'.');
System.out.println();
}
System.out.println();
}
public void tf(long[]... b)
{
if(INPUT.length() != 0) {
for (long[] r : b) {
for (long x : r) {
for (int i = 0; i < 64; i++) {
System.out.print(x << ~i < 0 ? '#' : '.');
}
}
System.out.println();
}
System.out.println();
}
}
public void tf(long... b)
{
if(INPUT.length() != 0) {
for (long x : b) {
for (int i = 0; i < 64; i++) {
System.out.print(x << ~i < 0 ? '#' : '.');
}
}
System.out.println();
}
}
private void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}