#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}

#define MD 1000000007

const char *filename[] = {".testcase001test_in01.txt", ".testcase001test_in02.txt", ".testcase001test_in03.txt", ".testcase001test_in04.txt", ".testcase001test_in05.txt", ".testcase001test_in06.txt", ".testcase001test_in07.txt", ".testcase001test_in08.txt", ".testcase001test_in09.txt", ".testcase001test_in10.txt", ".testcase001test_out01.txt", ".testcase001test_out02.txt", ".testcase001test_out03.txt", ".testcase001test_out04.txt", ".testcase001test_out05.txt", ".testcase001test_out06.txt", ".testcase001test_out07.txt", ".testcase001test_out08.txt", ".testcase001test_out09.txt", ".testcase001test_out10.txt", ".testcase002test_in01.txt", ".testcase002test_in02.txt", ".testcase002test_in03.txt", ".testcase002test_in04.txt", ".testcase002test_in05.txt", ".testcase002test_in06.txt", ".testcase002test_in07.txt", ".testcase002test_in08.txt", ".testcase002test_in09.txt", ".testcase002test_in10.txt", ".testcase002test_out01.txt", ".testcase002test_out02.txt", ".testcase002test_out03.txt", ".testcase002test_out04.txt", ".testcase002test_out05.txt", ".testcase002test_out06.txt", ".testcase002test_out07.txt", ".testcase002test_out08.txt", ".testcase002test_out09.txt", ".testcase002test_out10.txt", ".testcase003test_in1.txt", ".testcase003test_in10.txt", ".testcase003test_in11.txt", ".testcase003test_in12.txt", ".testcase003test_in13.txt", ".testcase003test_in14.txt", ".testcase003test_in15.txt", ".testcase003test_in16.txt", ".testcase003test_in17.txt", ".testcase003test_in18.txt", ".testcase003test_in19.txt", ".testcase003test_in2.txt", ".testcase003test_in20.txt", ".testcase003test_in3.txt", ".testcase003test_in4.txt", ".testcase003test_in5.txt", ".testcase003test_in6.txt", ".testcase003test_in7.txt", ".testcase003test_in8.txt", ".testcase003test_in9.txt", ".testcase003test_out1.txt", ".testcase003test_out10.txt", ".testcase003test_out11.txt", ".testcase003test_out12.txt", ".testcase003test_out13.txt", ".testcase003test_out14.txt", ".testcase003test_out15.txt", ".testcase003test_out16.txt", ".testcase003test_out17.txt", ".testcase003test_out18.txt", ".testcase003test_out19.txt", ".testcase003test_out2.txt", ".testcase003test_out20.txt", ".testcase003test_out3.txt", ".testcase003test_out4.txt", ".testcase003test_out5.txt", ".testcase003test_out6.txt", ".testcase003test_out7.txt", ".testcase003test_out8.txt", ".testcase003test_out9.txt", ".testcase004test_in01.txt", ".testcase004test_in02.txt", ".testcase004test_in03.txt", ".testcase004test_in04.txt", ".testcase004test_in05.txt", ".testcase004test_in06.txt", ".testcase004test_in07.txt", ".testcase004test_in08.txt", ".testcase004test_in09.txt", ".testcase004test_in10.txt", ".testcase004test_out01.txt", ".testcase004test_out02.txt", ".testcase004test_out03.txt", ".testcase004test_out04.txt", ".testcase004test_out05.txt", ".testcase004test_out06.txt", ".testcase004test_out07.txt", ".testcase004test_out08.txt", ".testcase004test_out09.txt", ".testcase004test_out10.txt", ".testcase005test_in1.txt", ".testcase005test_in10.txt", ".testcase005test_in11.txt", ".testcase005test_in12.txt", ".testcase005test_in13.txt", ".testcase005test_in14.txt", ".testcase005test_in15.txt", ".testcase005test_in16.txt", ".testcase005test_in17.txt", ".testcase005test_in18.txt", ".testcase005test_in19.txt", ".testcase005test_in2.txt", ".testcase005test_in20.txt", ".testcase005test_in3.txt", ".testcase005test_in4.txt", ".testcase005test_in5.txt", ".testcase005test_in6.txt", ".testcase005test_in7.txt", ".testcase005test_in8.txt", ".testcase005test_in9.txt", ".testcase005test_out1.txt", ".testcase005test_out10.txt", ".testcase005test_out11.txt", ".testcase005test_out12.txt", ".testcase005test_out13.txt", ".testcase005test_out14.txt", ".testcase005test_out15.txt", ".testcase005test_out16.txt", ".testcase005test_out17.txt", ".testcase005test_out18.txt", ".testcase005test_out19.txt", ".testcase005test_out2.txt", ".testcase005test_out20.txt", ".testcase005test_out3.txt", ".testcase005test_out4.txt", ".testcase005test_out5.txt", ".testcase005test_out6.txt", ".testcase005test_out7.txt", ".testcase005test_out8.txt", ".testcase005test_out9.txt", ".testcase006test_in01.txt", ".testcase006test_in02.txt", ".testcase006test_in03.txt", ".testcase006test_in04.txt", ".testcase006test_in05.txt", ".testcase006test_in06.txt", ".testcase006test_in07.txt", ".testcase006test_in08.txt", ".testcase006test_in09.txt", ".testcase006test_in10.txt", ".testcase006test_out01.txt", ".testcase006test_out02.txt", ".testcase006test_out03.txt", ".testcase006test_out04.txt", ".testcase006test_out05.txt", ".testcase006test_out06.txt", ".testcase006test_out07.txt", ".testcase006test_out08.txt", ".testcase006test_out09.txt", ".testcase006test_out10.txt", ".testcase007test_in01.txt", ".testcase007test_in02.txt", ".testcase007test_in03.txt", ".testcase007test_in04.txt", ".testcase007test_in05.txt", ".testcase007test_in06.txt", ".testcase007test_in07.txt", ".testcase007test_in08.txt", ".testcase007test_in09.txt", ".testcase007test_in10.txt", ".testcase007test_out01.txt", ".testcase007test_out02.txt", ".testcase007test_out03.txt", ".testcase007test_out04.txt", ".testcase007test_out05.txt", ".testcase007test_out06.txt", ".testcase007test_out07.txt", ".testcase007test_out08.txt", ".testcase007test_out09.txt", ".testcase007test_out10.txt", ".testcase008test_in01.txt", ".testcase008test_in02.txt", ".testcase008test_in03.txt", ".testcase008test_in04.txt", ".testcase008test_in05.txt", ".testcase008test_in06.txt", ".testcase008test_in07.txt", ".testcase008test_in08.txt", ".testcase008test_in09.txt", ".testcase008test_in10.txt", ".testcase008test_out01.txt", ".testcase008test_out02.txt", ".testcase008test_out03.txt", ".testcase008test_out04.txt", ".testcase008test_out05.txt", ".testcase008test_out06.txt", ".testcase008test_out07.txt", ".testcase008test_out08.txt", ".testcase008test_out09.txt", ".testcase008test_out10.txt", ".testcase009test_in01.txt", ".testcase009test_in02.txt", ".testcase009test_in03.txt", ".testcase009test_in04.txt", ".testcase009test_in05.txt", ".testcase009test_in06.txt", ".testcase009test_in07.txt", ".testcase009test_in08.txt", ".testcase009test_in09.txt", ".testcase009test_in10.txt", ".testcase009test_out01.txt", ".testcase009test_out02.txt", ".testcase009test_out03.txt", ".testcase009test_out04.txt", ".testcase009test_out05.txt", ".testcase009test_out06.txt", ".testcase009test_out07.txt", ".testcase009test_out08.txt", ".testcase009test_out09.txt", ".testcase009test_out10.txt", ".testcase010test_in01.txt", ".testcase010test_in02.txt", ".testcase010test_in03.txt", ".testcase010test_in04.txt", ".testcase010test_in05.txt", ".testcase010test_in06.txt", ".testcase010test_in07.txt", ".testcase010test_in08.txt", ".testcase010test_in09.txt", ".testcase010test_in10.txt", ".testcase010test_out01.txt", ".testcase010test_out02.txt", ".testcase010test_out03.txt", ".testcase010test_out04.txt", ".testcase010test_out05.txt", ".testcase010test_out06.txt", ".testcase010test_out07.txt", ".testcase010test_out08.txt", ".testcase010test_out09.txt", ".testcase010test_out10.txt", ".testcase011test_in01.txt", ".testcase011test_in02.txt", ".testcase011test_in03.txt", ".testcase011test_in04.txt", ".testcase011test_in05.txt", ".testcase011test_in06.txt", ".testcase011test_in07.txt", ".testcase011test_in08.txt", ".testcase011test_in09.txt", ".testcase011test_in10.txt", ".testcase011test_out01.txt", ".testcase011test_out02.txt", ".testcase011test_out03.txt", ".testcase011test_out04.txt", ".testcase011test_out05.txt", ".testcase011test_out06.txt", ".testcase011test_out07.txt", ".testcase011test_out08.txt", ".testcase011test_out09.txt", ".testcase011test_out10.txt", ".testcase012test_in01.txt", ".testcase012test_in02.txt", ".testcase012test_in03.txt", ".testcase012test_in04.txt", ".testcase012test_in05.txt", ".testcase012test_in06.txt", ".testcase012test_in07.txt", ".testcase012test_in08.txt", ".testcase012test_in09.txt", ".testcase012test_in10.txt", ".testcase012test_out01.txt", ".testcase012test_out02.txt", ".testcase012test_out03.txt", ".testcase012test_out04.txt", ".testcase012test_out05.txt", ".testcase012test_out06.txt", ".testcase012test_out07.txt", ".testcase012test_out08.txt", ".testcase012test_out09.txt", ".testcase012test_out10.txt", ".testcase013test_in01.txt", ".testcase013test_in02.txt", ".testcase013test_in03.txt", ".testcase013test_in04.txt", ".testcase013test_in05.txt", ".testcase013test_in06.txt", ".testcase013test_in07.txt", ".testcase013test_in08.txt", ".testcase013test_in09.txt", ".testcase013test_in10.txt", ".testcase013test_out01.txt", ".testcase013test_out02.txt", ".testcase013test_out03.txt", ".testcase013test_out04.txt", ".testcase013test_out05.txt", ".testcase013test_out06.txt", ".testcase013test_out07.txt", ".testcase013test_out08.txt", ".testcase013test_out09.txt", ".testcase013test_out10.txt", ".testcase014test_in01.txt", ".testcase014test_in02.txt", ".testcase014test_in03.txt", ".testcase014test_in04.txt", ".testcase014test_in05.txt", ".testcase014test_in06.txt", ".testcase014test_in07.txt", ".testcase014test_in08.txt", ".testcase014test_in09.txt", ".testcase014test_in10.txt", ".testcase014test_out01.txt", ".testcase014test_out02.txt", ".testcase014test_out03.txt", ".testcase014test_out04.txt", ".testcase014test_out05.txt", ".testcase014test_out06.txt", ".testcase014test_out07.txt", ".testcase014test_out08.txt", ".testcase014test_out09.txt", ".testcase014test_out10.txt", ".testcase015test_in01.txt", ".testcase015test_in02.txt", ".testcase015test_in03.txt", ".testcase015test_in04.txt", ".testcase015test_in05.txt", ".testcase015test_in06.txt", ".testcase015test_in07.txt", ".testcase015test_in08.txt", ".testcase015test_in09.txt", ".testcase015test_in10.txt", ".testcase015test_out01.txt", ".testcase015test_out02.txt", ".testcase015test_out03.txt", ".testcase015test_out04.txt", ".testcase015test_out05.txt", ".testcase015test_out06.txt", ".testcase015test_out07.txt", ".testcase015test_out08.txt", ".testcase015test_out09.txt", ".testcase015test_out10.txt", ".testcase016test_in01.txt", ".testcase016test_in02.txt", ".testcase016test_in03.txt", ".testcase016test_in04.txt", ".testcase016test_in05.txt", ".testcase016test_in06.txt", ".testcase016test_in07.txt", ".testcase016test_in08.txt", ".testcase016test_in09.txt", ".testcase016test_in10.txt", ".testcase016test_out01.txt", ".testcase016test_out02.txt", ".testcase016test_out03.txt", ".testcase016test_out04.txt", ".testcase016test_out05.txt", ".testcase016test_out06.txt", ".testcase016test_out07.txt", ".testcase016test_out08.txt", ".testcase016test_out09.txt", ".testcase016test_out10.txt", ".testcase017test_in01.txt", ".testcase017test_in02.txt", ".testcase017test_in03.txt", ".testcase017test_in04.txt", ".testcase017test_in05.txt", ".testcase017test_in06.txt", ".testcase017test_in07.txt", ".testcase017test_in08.txt", ".testcase017test_in09.txt", ".testcase017test_in10.txt", ".testcase017test_out01.txt", ".testcase017test_out02.txt", ".testcase017test_out03.txt", ".testcase017test_out04.txt", ".testcase017test_out05.txt", ".testcase017test_out06.txt", ".testcase017test_out07.txt", ".testcase017test_out08.txt", ".testcase017test_out09.txt", ".testcase017test_out10.txt", ".testcase018test_in01.txt", ".testcase018test_in02.txt", ".testcase018test_in03.txt", ".testcase018test_in04.txt", ".testcase018test_in05.txt", ".testcase018test_in06.txt", ".testcase018test_in07.txt", ".testcase018test_in08.txt", ".testcase018test_in09.txt", ".testcase018test_in10.txt", ".testcase018test_out01.txt", ".testcase018test_out02.txt", ".testcase018test_out03.txt", ".testcase018test_out04.txt", ".testcase018test_out05.txt", ".testcase018test_out06.txt", ".testcase018test_out07.txt", ".testcase018test_out08.txt", ".testcase018test_out09.txt", ".testcase018test_out10.txt", ".testcase019test_in01.txt", ".testcase019test_in02.txt", ".testcase019test_in03.txt", ".testcase019test_in04.txt", ".testcase019test_in05.txt", ".testcase019test_in06.txt", ".testcase019test_in07.txt", ".testcase019test_in08.txt", ".testcase019test_in09.txt", ".testcase019test_in10.txt", ".testcase019test_out01.txt", ".testcase019test_out02.txt", ".testcase019test_out03.txt", ".testcase019test_out04.txt", ".testcase019test_out05.txt", ".testcase019test_out06.txt", ".testcase019test_out07.txt", ".testcase019test_out08.txt", ".testcase019test_out09.txt", ".testcase019test_out10.txt", ".testcase020test_in01.txt", ".testcase020test_in02.txt", ".testcase020test_in03.txt", ".testcase020test_in04.txt", ".testcase020test_in05.txt", ".testcase020test_in06.txt", ".testcase020test_in07.txt", ".testcase020test_in08.txt", ".testcase020test_in09.txt", ".testcase020test_in10.txt", ".testcase020test_out01.txt", ".testcase020test_out02.txt", ".testcase020test_out03.txt", ".testcase020test_out04.txt", ".testcase020test_out05.txt", ".testcase020test_out06.txt", ".testcase020test_out07.txt", ".testcase020test_out08.txt", ".testcase020test_out09.txt", ".testcase020test_out10.txt"};
ull filehs1[] = {15274683064132374459ULL, 221642238620663745ULL, 16789522776313768391ULL, 6481534432089878870ULL, 5649727098207455245ULL, 13929896679089032471ULL, 1658361977540394126ULL, 10372827219707783687ULL, 1508413860478778516ULL, 18195274226906378930ULL, 50750796ULL, 53792943ULL, 45681558ULL, 55395ULL, 50360ULL, 50090014764ULL, 49745810ULL, 45681558ULL, 53800999ULL, 55825069ULL, 52374ULL, 49737754ULL, 50754824ULL, 55190679220ULL, 50436567415602ULL, 14251654377481291322ULL, 14698226282848336938ULL, 9767131329393737460ULL, 1467263708984623080ULL, 14246788804666503241ULL, 67418236952816346ULL, 67418236952816346ULL, 67418236952816346ULL, 67508382773ULL, 67508382773ULL, 67418236952816346ULL, 67508382773ULL, 67418236952816346ULL, 67508382773ULL, 67508382773ULL, 53381ULL, 55585191309994ULL, 57635647057311ULL, 55579064422915ULL, 54549742832940ULL, 50444735588353ULL, 56614502761493ULL, 58670076419148ULL, 58662927376719ULL, 58669051209567ULL, 50441673153324ULL, 49737754ULL, 14250617854721694449ULL, 52374ULL, 51466900016458ULL, 55197783605ULL, 54550769048514ULL, 51469960413319ULL, 50439630861659ULL, 53521451518763ULL, 52374ULL, 50436563363434ULL, 50438602611945ULL, 50435543234168ULL, 45681558ULL, 45681558ULL, 45681558ULL, 45681558ULL, 50439629849624ULL, 50440649977883ULL, 52131302450ULL, 57409ULL, 50441665038918ULL, 45681558ULL, 45681558ULL, 50091034855ULL, 45681558ULL, 45681558ULL, 52128256275ULL, 56215883766ULL, 11675703944871866395ULL, 9021053209535191488ULL, 16387635489772488723ULL, 7755099281497437597ULL, 11339180531197521588ULL, 5313714364198658418ULL, 1314497983914883044ULL, 4315174667137681015ULL, 3879808380073717025ULL, 9532158858530489519ULL, 12912732785144693193ULL, 7352528569263444757ULL, 7352528569263444757ULL, 12912732785144693193ULL, 12912732785144693193ULL, 12912732785144693193ULL, 7352528569263444757ULL, 12912732785144693193ULL, 7352528569263444757ULL, 12912732785144693193ULL, 5178788709324521107ULL, 17684901236499210033ULL, 16751319528760501548ULL, 7616799247824683183ULL, 480296397419233857ULL, 3027337478265910821ULL, 1721927922920406638ULL, 16043954364318038820ULL, 12389094460664856587ULL, 9535409498989704605ULL, 8154031630816792990ULL, 3818911438893673628ULL, 3597665566677171092ULL, 50749511659222203ULL, 5191651324849110012ULL, 8607526933835928138ULL, 15895290696385754802ULL, 7133045720584857828ULL, 10725076192746249834ULL, 690924137998616792ULL, 50360ULL, 53802006ULL, 50086971610ULL, 56842139ULL, 50085958568ULL, 50085963603ULL, 49744803ULL, 50751803ULL, 50085964610ULL, 50088998701ULL, 50086977652ULL, 53381ULL, 50089005750ULL, 49353ULL, 50085962596ULL, 55830104ULL, 50085962596ULL, 50085956554ULL, 56840125ULL, 50084942505ULL, 50396734556833ULL, 14250578780518652820ULL, 15244018582511689235ULL, 18083916054460691685ULL, 1563027353070223652ULL, 13317491921798438976ULL, 1465447128314260074ULL, 7772164455652486591ULL, 2227708094100073223ULL, 12351469855821857240ULL, 51367ULL, 51765852ULL, 51367ULL, 52864716309116510ULL, 57004635530777720ULL, 54937760808100430ULL, 14253730505842206941ULL, 14252697072061482364ULL, 14254759834624819414ULL, 14259940385698890260ULL, 53381ULL, 49738761ULL, 50788585900834953ULL, 51465879882157ULL, 50435544244189ULL, 50435542220119ULL, 54549743844975ULL, 53521448472588ULL, 51469966502648ULL, 55581102665433ULL, 88946404766ULL, 78263912526901ULL, 88946404766ULL, 88946404766ULL, 88946404766ULL, 78263912526901ULL, 88946404766ULL, 88946404766ULL, 88946404766ULL, 78263912526901ULL, 14211271161520578431ULL, 14211270134246353387ULL, 9856464912662020528ULL, 10456905389001132311ULL, 9000410795298521499ULL, 422922973601698385ULL, 5186745508816406036ULL, 3065909989410236618ULL, 7962861946883943661ULL, 8779098881355327996ULL, 78263912526901ULL, 88946404766ULL, 2931683241948060345ULL, 17461391144785279435ULL, 14952979299718364159ULL, 6049287733737934520ULL, 6049287733737934520ULL, 6049287733737934520ULL, 6049287733737934520ULL, 6049287733737934520ULL, 1326487703897689981ULL, 1288809647749199779ULL, 10590453169194084882ULL, 7130174535418009089ULL, 13493266512348979323ULL, 17611514184801493305ULL, 3956714646468578617ULL, 16025563439782010483ULL, 18378511912006695881ULL, 13730076438903348861ULL, 50360ULL, 50360ULL, 53381ULL, 52374ULL, 53381ULL, 53381ULL, 52374ULL, 51367ULL, 52374ULL, 53381ULL, 6344453608651927175ULL, 13657084518128602767ULL, 902596199627037941ULL, 3793160498620675612ULL, 4425512732324410968ULL, 13374010626137178544ULL, 16882635907679594806ULL, 7931917624207728169ULL, 5731864804034193379ULL, 14935477210488961488ULL, 43951969118ULL, 43647418ULL, 42632362ULL, 4183570173751788332ULL, 2299157100046457663ULL, 16191497443317921344ULL, 1979793692149631563ULL, 7296169029564129918ULL, 12864016234042370560ULL, 12234774853084714430ULL, 5557658275979703214ULL, 16138818160501324699ULL, 10004866308592457116ULL, 15507596010686261302ULL, 5877782730227022097ULL, 1729258589832583683ULL, 12813449975741203122ULL, 8549696058343048308ULL, 13130107981988053799ULL, 13419815205471470251ULL, 53381ULL, 50757845ULL, 52786950ULL, 51367ULL, 2003875659856610683ULL, 48346ULL, 10830888228102430294ULL, 1615141210884208279ULL, 1298448990417872451ULL, 5529310033930027850ULL, 50046413678ULL, 9021053209535191488ULL, 51785004102407759ULL, 4844686466584307000ULL, 51785005123555102ULL, 4803236516307528993ULL, 8794683974137385477ULL, 5260457450887734085ULL, 17321016294041483650ULL, 16343258580949734000ULL, 50360ULL, 50090020806ULL, 45681558ULL, 3929327690614162630ULL, 57853167ULL, 51107105911ULL, 53155482877ULL, 54170549954ULL, 50089000715ULL, 50090020806ULL, 844960125442436145ULL, 1650134114829656834ULL, 12607598234321324368ULL, 17329837823470165095ULL, 12944816048639648896ULL, 5964214922173966454ULL, 3106759706504682494ULL, 13112096900876583501ULL, 6994385445419336597ULL, 1882688349678294889ULL, 12912732785144693193ULL, 12912732785144693193ULL, 7352528569263444757ULL, 12912732785144693193ULL, 12912732785144693193ULL, 7352528569263444757ULL, 12912732785144693193ULL, 7352528569263444757ULL, 7352528569263444757ULL, 12912732785144693193ULL, 9021053209535191488ULL, 10597374081379112572ULL, 17909857728357198674ULL, 2773385785930461589ULL, 3193246221104072813ULL, 9850695824620039593ULL, 9609763068399175265ULL, 12555267814918674036ULL, 7274173094611927310ULL, 17773511353439031852ULL, 16441416606884777467ULL, 9534253096794121975ULL, 1053686470726174663ULL, 18125578711673174194ULL, 4813883575052615044ULL, 6740921666142700347ULL, 4515918448055415718ULL, 7626603414646751277ULL, 10684690720914673910ULL, 2287775447378208944ULL, 4288327270016755682ULL, 3645330566955684230ULL, 4329240837055797545ULL, 14398142541396455774ULL, 12857319475171242440ULL, 722234157296165477ULL, 12549266830987833696ULL, 18042112059121799311ULL, 16615282072858109836ULL, 12043943599031143350ULL, 50360ULL, 16440381114463903003ULL, 7164063390209564071ULL, 9024225787789453070ULL, 13520749768105624446ULL, 6429815354477887786ULL, 1697512047616485538ULL, 15619996649830787703ULL, 15349690116500229195ULL, 7201816562863797183ULL, 1596356535152796649ULL, 3018643853378924831ULL, 7647167198187670671ULL, 13497790041724807815ULL, 11946274417859186669ULL, 199054979474547365ULL, 13405677641268698062ULL, 16706470841596517644ULL, 1603761325739056637ULL, 8569585740658140167ULL, 49740775ULL, 15298540303956085994ULL, 15301647813599688215ULL, 17388167102341127545ULL, 4146847535416037723ULL, 3108247610008777455ULL, 57007721438054308ULL, 4155134569888740446ULL, 18421588531221759048ULL, 4149958130969952637ULL, 4414713852353288077ULL, 12582409614857452908ULL, 5714654990713529026ULL, 6607564072609462763ULL, 3179279440941612877ULL, 16075045903800071578ULL, 11500739313785696772ULL, 1476075045891526742ULL, 17274868972951276390ULL, 13305231141054493638ULL, 50084947540ULL, 49743796ULL, 50435537140811ULL, 51465881913276ULL, 50089001722ULL, 50092041855ULL, 51110153093ULL, 53148385541ULL, 51106093876ULL, 53151435744ULL, 67463734407ULL, 9530909527363669757ULL, 15814103825862943882ULL, 4201369888000524140ULL, 12785466090219422672ULL, 1108219974593760988ULL, 12126659993052231022ULL, 17751613453337696870ULL, 1501816139139325228ULL, 16185012185154509320ULL, 66440555945ULL, 435970197386930986ULL, 5939837046428701974ULL, 1565762943144626546ULL, 16551729377558179905ULL, 18259926144895848636ULL, 2461874243349524730ULL, 7368062646429552739ULL, 7790930255105561580ULL, 3546759493162318550ULL, 6824004446914198287ULL, 11475594225999803281ULL, 4372005613188665673ULL, 13681863056633631430ULL, 9258727671099527047ULL, 16166734221471539784ULL, 8618924918936342168ULL, 5516236330390070141ULL, 3079610877422732090ULL, 8112606255827086987ULL, 58252098186ULL, 55188651122ULL, 51465872786835ULL, 56606328511497ULL, 15299573745910053567ULL, 14256833901279106005ULL, 14259938328077869688ULL, 15299578883302341235ULL, 16339208133404578429ULL, 17378852797725958208ULL, 12443484354337061898ULL, 17041322555028892651ULL, 8200250138381584924ULL, 3017347205898459099ULL, 3762286523858222659ULL, 16466775523343743711ULL, 6490611473073051815ULL, 10833387400194991368ULL, 9019994141366231382ULL, 1404933375660647568ULL, 90952166499ULL, 90952166499ULL, 79175385ULL, 79175385ULL, 90952166499ULL, 90952166499ULL, 79175385ULL, 90952166499ULL, 79175385ULL, 79175385ULL};
ull filehs2[] = {3643024644895116507ULL, 563575967383922889ULL, 16421161026138196623ULL, 16233319384467894702ULL, 13541241135924324221ULL, 7003665434700801895ULL, 4654526873397251870ULL, 18915124322240127ULL, 3297543077132565732ULL, 3666466858825665666ULL, 197573699643948ULL, 209428115897631ULL, 177816341208974ULL, 109330715ULL, 99391560ULL, 15953404514852723332ULL, 193622245449866ULL, 177816341208974ULL, 209428131800279ULL, 217331068018077ULL, 103367222ULL, 193622229547218ULL, 197573707595272ULL, 18334190136694107588ULL, 12790159635843093154ULL, 9450824269126974946ULL, 9272522353348793370ULL, 14695992674069263932ULL, 14681792480817722680ULL, 1726518552107656209ULL, 97818246984592082ULL, 97818246984592082ULL, 97818246984592082ULL, 1912279101177243077ULL, 1912279101177243077ULL, 97818246984592082ULL, 1912279101177243077ULL, 97818246984592082ULL, 1912279101177243077ULL, 1912279101177243077ULL, 105355053ULL, 9852367709369230938ULL, 9652091780814425431ULL, 18063447698542059147ULL, 14414231388834125596ULL, 1842049032148522305ULL, 13501544504360294541ULL, 15682121372686225644ULL, 16038338705073919087ULL, 7827246861460983223ULL, 15170965015050863708ULL, 193622229547218ULL, 13203649748751962577ULL, 103367222ULL, 5847451062453557994ULL, 18334217797010626501ULL, 3822365777805998314ULL, 10965271250296720775ULL, 17907991678116424435ULL, 173165273994354331ULL, 103367222ULL, 12790143829962706234ULL, 10053105312478903993ULL, 4935289076117764928ULL, 177816341208974ULL, 177816341208974ULL, 177816341208974ULL, 177816341208974ULL, 17907987726648315536ULL, 7316098406781717395ULL, 13216373900334956354ULL, 113306377ULL, 15170933403270211558ULL, 177816341208974ULL, 177816341208974ULL, 15953408466336734879ULL, 177816341208974ULL, 177816341208974ULL, 13216362045910751347ULL, 7742320574199859238ULL, 5111597878206859539ULL, 4831000525498353360ULL, 9201340649545941251ULL, 13453094640270474893ULL, 16914454191318485076ULL, 1353024465773776818ULL, 1937127728976253588ULL, 14323549222596430327ULL, 18364207745948837185ULL, 7732954474117533351ULL, 4601292907360200177ULL, 5739508678375694165ULL, 5739508678375694165ULL, 4601292907360200177ULL, 4601292907360200177ULL, 4601292907360200177ULL, 5739508678375694165ULL, 4601292907360200177ULL, 5739508678375694165ULL, 4601292907360200177ULL, 1586207709180909579ULL, 1984638715872975033ULL, 11903813862021168164ULL, 10074722219333741639ULL, 13489257793006148401ULL, 7589771172047294469ULL, 6631376434966375854ULL, 71301934618596324ULL, 16049429288027868691ULL, 2090736980959881909ULL, 4096791626340922270ULL, 15492128830668666228ULL, 14981807744673991380ULL, 17025709500648210659ULL, 16927896097586855820ULL, 7214607945248799898ULL, 9608593142767645010ULL, 1235429379082711428ULL, 8390343319749175738ULL, 14734767761336472088ULL, 99391560ULL, 209428133788110ULL, 15953392660434481818ULL, 221282546066131ULL, 15953388708964385088ULL, 15953388708974324243ULL, 193622243462035ULL, 197573701631779ULL, 15953388708976312074ULL, 15953400563376663109ULL, 15953392660446408804ULL, 105355053ULL, 15953400563390577926ULL, 97403729ULL, 15953388708972336412ULL, 217331077957232ULL, 15953388708972336412ULL, 15953388708960409426ULL, 221282542090469ULL, 15953384757488324865ULL, 1598543695745132073ULL, 14852973603759162556ULL, 3545456971919143715ULL, 14215308352675107301ULL, 11684007071783903524ULL, 1581753288162401912ULL, 13567875207394582802ULL, 4652767269127074999ULL, 6896726108932585183ULL, 2946832252879447208ULL, 101379391ULL, 201525173716340ULL, 101379391ULL, 13700654311456068446ULL, 8213599996892837480ULL, 16786892671911677014ULL, 10511949684626456245ULL, 14620511064791433220ULL, 12277985584746115630ULL, 10136238772526816332ULL, 105355053ULL, 193622231535049ULL, 15376535801653773745ULL, 16439340382308229149ULL, 4935293027581898165ULL, 4935285124645680367ULL, 14414235340302234495ULL, 173153419570149324ULL, 10965294959139167296ULL, 15326405229602074993ULL, 843591540807146150ULL, 17303868947000667285ULL, 843591540807146150ULL, 843591540807146150ULL, 843591540807146150ULL, 17303868947000667285ULL, 843591540807146150ULL, 843591540807146150ULL, 843591540807146150ULL, 17303868947000667285ULL, 17222947193006024399ULL, 10836723977598916419ULL, 1408547243503552592ULL, 8905902273372168687ULL, 16096689649789832131ULL, 7719923164014398089ULL, 7521492701333413340ULL, 9970834408561001394ULL, 11043315807374279373ULL, 17869238689716077500ULL, 17303868947000667285ULL, 843591540807146150ULL, 5755546568850716073ULL, 7928295358482143555ULL, 5038279324881515871ULL, 4856992968924444504ULL, 4856992968924444504ULL, 4856992968924444504ULL, 4856992968924444504ULL, 4856992968924444504ULL, 13693278943411479573ULL, 3115399048639292731ULL, 4403900707831649034ULL, 17925408659122021033ULL, 5004449761734585579ULL, 4275889045136118089ULL, 11304956929809405745ULL, 7175844009384599195ULL, 17414589940291134921ULL, 2628429786172731973ULL, 99391560ULL, 99391560ULL, 105355053ULL, 103367222ULL, 105355053ULL, 105355053ULL, 103367222ULL, 101379391ULL, 103367222ULL, 105355053ULL, 3607610630220694583ULL, 3155815670178673207ULL, 703228838051540589ULL, 7541900736170118292ULL, 12578560721347105056ULL, 10124966432414167512ULL, 13941437777626864398ULL, 2131358397355281033ULL, 11302128275005158787ULL, 14603243909897750888ULL, 5717696964115118430ULL, 169913385112866ULL, 165961911040474ULL, 6388828705563088580ULL, 14669821622352411599ULL, 4838175444135294224ULL, 5383824675123967635ULL, 2170550486223386094ULL, 3417190154278434352ULL, 12671746213420066534ULL, 5425234902872172670ULL, 2015637062443317115ULL, 14369907694993785108ULL, 15538169701658548838ULL, 17620471606371121577ULL, 6267768956784402091ULL, 11163089846352001898ULL, 7225104381990069180ULL, 628485652572084031ULL, 2150058318085004315ULL, 105355053ULL, 197573713558765ULL, 205476659715718ULL, 101379391ULL, 9382613421627060715ULL, 95415898ULL, 15497237462441588502ULL, 13538547748650996943ULL, 595911458001939403ULL, 14127785557392884050ULL, 15953234601559050702ULL, 4831000525498353360ULL, 1768911744186985463ULL, 10974813251836681840ULL, 9623770449511962654ULL, 12963124739353017449ULL, 2122306263125263949ULL, 705709073224857197ULL, 11941475225989175586ULL, 17896045583915582320ULL, 99391560ULL, 15953404514864650318ULL, 177816341208974ULL, 10170289205520248846ULL, 225234012187199ULL, 5361503340579810663ULL, 2624500386348745133ULL, 10479335382849166282ULL, 15953400563380638771ULL, 15953404514864650318ULL, 6187999014988377609ULL, 11449043732912043650ULL, 17396801200237218000ULL, 12400530870296587663ULL, 11600095027906075600ULL, 11864151968860057814ULL, 9771776947825839534ULL, 12484179286345341333ULL, 7634100002246659373ULL, 7540659586861980625ULL, 4601292907360200177ULL, 4601292907360200177ULL, 5739508678375694165ULL, 4601292907360200177ULL, 4601292907360200177ULL, 5739508678375694165ULL, 4601292907360200177ULL, 5739508678375694165ULL, 5739508678375694165ULL, 4601292907360200177ULL, 4831000525498353360ULL, 957017775799239980ULL, 12665142815105297018ULL, 15538977313622462693ULL, 987078843838786957ULL, 17930923245505989441ULL, 1107758975708840497ULL, 11021593809815447676ULL, 14889032584693034550ULL, 18151064110752433796ULL, 17908877432600500099ULL, 15564101711133366655ULL, 16321161811069129263ULL, 7721647840364086786ULL, 7013777763759893916ULL, 8647107624617734915ULL, 1348723120205870510ULL, 1300942117827529837ULL, 11690485392334483550ULL, 5524104259271590432ULL, 17154138409264326370ULL, 16593935013181496550ULL, 15062610608822892833ULL, 1628457208785452718ULL, 10161722570871594232ULL, 15350532683224051285ULL, 729036070654785264ULL, 15052339156394619567ULL, 3861797274597592764ULL, 8884973123941879798ULL, 99391560ULL, 14719018047742009683ULL, 4631346518228030615ULL, 14717014796046617094ULL, 3689907219053314190ULL, 17176726308573602730ULL, 15181144802614447314ULL, 6265016373606352871ULL, 4433380434091346211ULL, 14956203784113507807ULL, 4814315720989375217ULL, 1213636353059171095ULL, 9129118194143785543ULL, 2216337209547908183ULL, 4102213954321869909ULL, 5157874868686562293ULL, 7882506633516055230ULL, 9840369289532428740ULL, 7857112229419473469ULL, 3367384335207509367ULL, 193622235510711ULL, 3235443666399374202ULL, 3125310293356232591ULL, 9108995211506621313ULL, 7453124162914559283ULL, 14710132649941707647ULL, 3451472243309269308ULL, 6669911079336724918ULL, 16766176016052830632ULL, 2580874890692176197ULL, 14482128160118709141ULL, 657647466462472204ULL, 17331151999611085538ULL, 3994207921229764099ULL, 3381276168403129669ULL, 14337964584726074938ULL, 14134181799948132100ULL, 11306150319450899158ULL, 14058548709272653934ULL, 16194364259570941950ULL, 15953384757498264020ULL, 193622241474204ULL, 4935265367267367083ULL, 16439348285258361764ULL, 15953400563382626602ULL, 15953412417794904623ULL, 5361515195006003501ULL, 2624472726046141037ULL, 5361499389111701764ULL, 2624484580478297368ULL, 1912105236345887463ULL, 5858766522978517181ULL, 13688006335132359242ULL, 5483832347895818988ULL, 10088881904049335584ULL, 3218469862385869700ULL, 11270376469041760150ULL, 4134127634430820854ULL, 7922992226887577172ULL, 18055810564099543312ULL, 12503982701780329273ULL, 12459784544059460890ULL, 6518900760942200054ULL, 9924910873974862322ULL, 16201393133649354289ULL, 512281967047039908ULL, 7721259629889882418ULL, 4406763902011539891ULL, 2427009042323078388ULL, 10557107388041476734ULL, 4846313140894871319ULL, 17152648385844861561ULL, 16041769519958184113ULL, 17483273937868876158ULL, 8088678608167304295ULL, 2020979933883360456ULL, 15423742702836757512ULL, 1914261951551239469ULL, 18431544047719298650ULL, 18157061411942019587ULL, 5005270202315705962ULL, 18334182233749938466ULL, 16439312722009600715ULL, 6002887325526721225ULL, 6625535513609800799ULL, 922846338550435053ULL, 10692668809904035320ULL, 9518022148581032123ULL, 9501091033368532605ULL, 15424593159980312360ULL, 7611748928495018922ULL, 5297697116089897307ULL, 14703480228599347060ULL, 1547049564932904571ULL, 6839902581824829851ULL, 14773343026696489151ULL, 10489221498008965783ULL, 14194432194550181656ULL, 17257464176146538918ULL, 17648538131093291720ULL, 16553166698408384899ULL, 16553166698408384899ULL, 308214979634417ULL, 308214979634417ULL, 16553166698408384899ULL, 16553166698408384899ULL, 308214979634417ULL, 16553166698408384899ULL, 308214979634417ULL, 308214979634417ULL};

int main(){
  int i, j, k;
  int num_files = sizeof(filehs1) / sizeof(filehs1[0]); // 440
  ull hs1 = 0, hs2 = 0;
  int res[21] = {}, ress;

  for(;;){
    k = getchar();
    if(k==EOF) break;
    hs1 = hs1 * 1007 + k;
    hs2 = hs2 * 1987831 + k;
  }

  rep(i,num_files){
    if(hs1 != filehs1[i]) continue;
    if(hs2 != filehs2[i]) continue;
    res[atoi(filename[i]+9)] = 1;
  }

  ress = 0;
  rep(i,21) if(res[i]) res[ress++] = i;
  writerArr(res,ress);

  return 0;
}