/* POTM ENTRY: knight.c */
/* Your Name: Staffan Ulfberg */
/* Your email: staffanu@nada.kth.se */
#define __USE_FIXED_PROTOTYPES__
#include
#include
#include
#include
#include
int getrusage(int, struct rusage *);
void kruskal(void);
void twoopt(void);
void lin_kernighan(void);
void random_path(void);
#define SIZE 100
#define EXTRA 6
#define MAX_TIME 580
#define abs(a) ((a)<0?-(a):(a))
#define swap(a, b) (a ^= b, b ^= a, a ^= b)
#define wrap(a) ((a)<0?(a)+n:(a)>=n?(a)-n:a)
short dx[8] = { -1, -2, -2, -1, 1, 2, 2, 1};
short dy[8] = { -2, -1, 1, 2, 2, 1, -1, -2};
extern unsigned char disttohome[SIZE+EXTRA][SIZE+EXTRA];
short visited[SIZE+EXTRA][SIZE+EXTRA];
short dist[101][101];
short n, x[101], y[101], path[101], saved_path[101];
double u[97];
int uni_i, uni_j;
void inituni(int seed) {
int i;
srand(seed);
for (i = 0; i < 97; i++)
u[i] = (rand() % 1000) / 1000.0;
uni_i = 0, uni_j = 97-33;
}
double uni(void) {
double r;
u[uni_i] = (r = u[uni_i]-u[uni_j], r += r < 0);
uni_i = (uni_i + 1) % 97;
uni_j = (uni_j + 1) % 97;
return r;
}
short distance(short x1, short y1, short x2, short y2) {
if (abs(x1-x2) == 1 && abs(y1-y2) == 1)
return !x1 && !y1 || !x2 && !y2 ? 4 : 2;
else
return disttohome[abs(x1-x2)][abs(y1-y2)];
}
void strokepath(short x1, short y1, short x2, short y2, int print,
short *steps, short *uhit) {
short force, k, v, d;
if (x1 == x2 && y1 == y2) return;
d = uni() > .5;
for (force = 0; force <= 1; force++)
for (k = d ? 7 : 0; k >= 0 && k <= 7; d ? k-- : k++)
if (x1+dx[k]>=0 && y1+dy[k]>=0
&& x1+dx[k]=0 && j+dy[k]>=0
&& i+dx[k] 1+disttohome[i][j])
changed = disttohome[i+dx[k]][j+dy[k]] = 1+disttohome[i][j];
}
} while (changed);
for (i = 0; i < 106; i++) {
for (j = 0; j < 106; j++)
printf("%c", 32+disttohome[i][j]);
printf("\n");
}*/
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
dist[i][j] = distance(x[i], y[i], x[j], y[j]);
kruskal(); twoopt(); lin_kernighan();
save_path(); beststeps = path_len(); j = 0;
while (getrusage(RUSAGE_SELF, &rusage),
rusage.ru_utime.tv_sec + rusage.ru_stime.tv_sec < MAX_TIME
&& j < 10) {
random_path(); lin_kernighan();
if ((steps = path_len()) < beststeps)
save_path(), beststeps = steps, j = 0;
if (steps == beststeps)
j++;
}
restore_path();
for (beststeps = 10000, bestuhit = i = 0, ibest = 0;
i < 6 || i < 100 && bestuhit-beststeps; i++) {
inituni(i);
printpath(0, &steps, &uhit);
if (steps < beststeps || steps == beststeps && uhit >= bestuhit)
ibest = i, beststeps = steps, bestuhit = uhit;
}
inituni(ibest);
printpath(1, &steps, &uhit);
}
short sets[101][101];
short flag[101];
#define clearflag() memset(flag, 0, sizeof(*flag) * n);
void initsets(void) {
int i, j;
for (i = 0; i < n; i++)
for (j = 0; j < 101; j++)
sets[i][j] = -1;
}
int _isconnected(int a, int b) {
int i;
if (flag[a]) return 0;
if (a == b) return 1;
flag[a] = 1;
for (i = 0; sets[a][i] >= 0; i++)
if (_isconnected(sets[a][i], b))
return 1;
return 0;
}
int isconnected(int a, int b) {
clearflag();
return _isconnected(a, b);
}
void unionsets(int a, int b) {
int i;
for (i = 0; sets[a][i] >= 0; i++);
sets[a][i] = b;
for (i = 0; sets[b][i] >= 0; i++);
sets[b][i] = a;
}
int c = 0;
void _visitall(int a) {
int i;
if (flag[a]) return;
flag[a] = 1;
path[c++] = a;
for (i = 0; sets[a][i] >= 0; i++)
_visitall(sets[a][i]);
}
struct edge {
short a, b, w;
} edges[101*101];
int comp(struct edge *x, struct edge *y) {
return x->w - y->w;
}
void kruskal(void) {
int i, j, k = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
edges[k].a = i, edges[k].b = j, edges[k++].w = dist[i][j];
qsort(edges, k, sizeof(struct edge), (int (*)()) comp);
initsets();
for (i = 0; i < k; i++)
if (!isconnected(edges[i].a, edges[i].b))
unionsets(edges[i].a, edges[i].b);
c = 0;
clearflag();
_visitall(0);
}
void swappath(int i, int j) {
int k, l, a, b;
l = wrap(j-i+1) / 2;
for (k = 0; k < l; k++)
a = wrap(i+k), b = wrap(j-k), swap(path[a], path[b]);
}
void twoopt(void) {
int i, j, i2, j2, change;
do {
change = 0;
for (i = 0; i < n; i++)
for (j = i + 2; j < n; j++) {
i2 = wrap(i + 1), j2 = wrap(j + 1);
if (dist[path[i]][path[i2]]+dist[path[j]][path[j2]]
> dist[path[i]][path[j]]+dist[path[i2]][path[j2]])
swappath(i + 1, j), change = 1;
}
} while (change);
}
int best;
void _lin_kernighan(int home, int remote, int sum) {
int thisbest = 0, u, v = 0, this, min = 100000, i, oldbest, wr, wr2;
int uu, vv, ruv;
flag[home] = flag[remote] = 1;
wr = wrap(remote+1); wr2 = wrap(remote-1);
for (i = 0; i < n; i++)
if (!flag[i] && i != wr && i != wr2 && dist[path[i]][path[remote]] < min)
min = dist[path[i]][path[remote]], v = i;
if (min == 100000)
return;
flag[v] = 1;
u = wrap(v + home - remote);
sum -= dist[path[remote]][path[v]];
this = sum + dist[path[u]][path[v]] - dist[path[u]][path[home]];
if (this > best)
thisbest = 1, best = this;
oldbest = best;
if (thisbest || sum > best) {
uu = u, vv = v;
if (uu < remote) uu += n;
if (vv < remote) vv += n;
ruv = uu < vv;
if (ruv) swappath(remote, u); else swappath(u, remote);
_lin_kernighan(home, remote, sum + dist[path[v]][path[remote]]);
if (!thisbest && oldbest == best)
if (ruv) swappath(remote, u); else swappath(u, remote);
}
}
void lin_kernighan(void) {
int i, j, changed;
do {
changed = 0;
for (i = 0; i < n; i++)
for (j = -1; j <= 1; j+= 2) {
best = 0;
clearflag();
_lin_kernighan(i, wrap(i+j), dist[path[i]][path[wrap(i+j)]]);
if (best) changed = 1;
}
} while (changed);
}
void random_path(void) {
int i, j;
for (i = 0; i < n; i++)
path[i] = i;
for (i = n - 1; i > 1; i--)
j = i * uni(), swap(path[i], path[j]);
}
unsigned char disttohome[106][106] = {
" #\"#\"#$%$%&'&'()()*+*+,-,-././01012323454567678989:;:;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"#$!\"#$#$%&%&'('()*)*+,+,-.-./0/012123434565678789:9:;<;<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV" ,
"\"!$#\"#$%$%&'&'()()*+*+,-,-././01012323454567678989:;:;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"#\"#\"#$#$%&%&'('()*)*+,+,-.-./0/012123434565678789:9:;<;<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"\"#\"#$#$%$%&'&'()()*+*+,-,-././01012323454567678989:;:;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"#$#$#$%$%&%&'('()*)*+,+,-.-./0/012123434565678789:9:;<;<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"$#$#$%$%&%&'&'()()*+*+,-,-././01012323454567678989:;:;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"%$%$%$%&%&'&'('()*)*+,+,-.-./0/012123434565678789:9:;<;<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"$%$%$%&%&'&'('()()*+*+,-,-././01012323454567678989:;:;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"%&%&%&%&'&'('()()*)*+,+,-.-./0/012123434565678789:9:;<;<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"&%&%&%&'&'('()()*)*+*+,-,-././01012323454567678989:;:;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"'&'&'&'&'('()()*)*+*+,+,-.-./0/012123434565678789:9:;<;<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"&'&'&'&'('()()*)*+*+,+,-,-././01012323454567678989:;:;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"'('('('('()()*)*+*+,+,-,-.-./0/012123434565678789:9:;<;<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"('('('('()()*)*+*+,+,-,-.-././01012323454567678989:;:;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
")()()()()()*)*+*+,+,-,-.-././0/012123434565678789:9:;<;<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"()()()()()*)*+*+,+,-,-.-././0/01012323454567678989:;:;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
")*)*)*)*)*)*+*+,+,-,-.-././0/01012123434565678789:9:;<;<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"*)*)*)*)*)*+*+,+,-,-.-././0/0101212323454567678989:;:;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"+*+*+*+*+*+*+,+,-,-.-././0/0101212323434565678789:9:;<;<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"*+*+*+*+*+*+,+,-,-.-././0/010121232343454567678989:;:;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"+,+,+,+,+,+,+,-,-.-././0/010121232343454565678789:9:;<;<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
",+,+,+,+,+,+,-,-.-././0/01012123234345456567678989:;:;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"-,-,-,-,-,-,-,-.-././0/01012123234345456567678789:9:;<;<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
",-,-,-,-,-,-,-.-././0/0101212323434545656767878989:;:;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"-.-.-.-.-.-.-.-././0/0101212323434545656767878989:9:;<;<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
".-.-.-.-.-.-.-././0/0101212323434545656767878989:9:;:;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"/././././././././0/0101212323434545656767878989:9:;:;<;<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"././././././././0/0101212323434545656767878989:9:;:;<;<=<=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"/0/0/0/0/0/0/0/0/0101212323434545656767878989:9:;:;<;<=<=>=>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"0/0/0/0/0/0/0/0/0101212323434545656767878989:9:;:;<;<=<=>=>?>?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"1010101010101010101212323434545656767878989:9:;:;<;<=<=>=>?>?@?@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"010101010101010101212323434545656767878989:9:;:;<;<=<=>=>?>?@?@A@ABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"12121212121212121212323434545656767878989:9:;:;<;<=<=>=>?>?@?@A@ABABCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"2121212121212121212323434545656767878989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"323232323232323232323434545656767878989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"23232323232323232323434545656767878989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"3434343434343434343434545656767878989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"434343434343434343434545656767878989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"54545454545454545454545656767878989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"4545454545454545454545656767878989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJKJKLMLMNONOPQPQRSRSTUTU",
"565656565656565656565656767878989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKLKLMNMNOPOPQRQRSTSTUV",
"65656565656565656565656767878989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLMLMNONOPQPQRSRSTUTU",
"7676767676767676767676767878989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMNMNOPOPQRQRSTSTUV",
"676767676767676767676767878989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNONOPQPQRSRSTUTU",
"78787878787878787878787878989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNOPOPQRQRSTSTUV",
"8787878787878787878787878989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPQPQRSRSTUTU",
"989898989898989898989898989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQRQRSTSTUV",
"89898989898989898989898989:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRSRSTUTU",
"9:9:9:9:9:9:9:9:9:9:9:9:9:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSTSTUV",
":9:9:9:9:9:9:9:9:9:9:9:9:9:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTUTU",
";:;:;:;:;:;:;:;:;:;:;:;:;:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUV",
":;:;:;:;:;:;:;:;:;:;:;:;:;:;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTU",
";<;<;<;<;<;<;<;<;<;<;<;<;<;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUV",
"<;<;<;<;<;<;<;<;<;<;<;<;<;<;<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVU",
"=<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUV",
"<=<=<=<=<=<=<=<=<=<=<=<=<=<=<=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVW",
"=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWV",
">=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVW",
"?>?>?>?>?>?>?>?>?>?>?>?>?>?>?>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWX",
">?>?>?>?>?>?>?>?>?>?>?>?>?>?>?>?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXW",
"?@?@?@?@?@?@?@?@?@?@?@?@?@?@?@?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWX",
"@?@?@?@?@?@?@?@?@?@?@?@?@?@?@?@?@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXY",
"A@A@A@A@A@A@A@A@A@A@A@A@A@A@A@A@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYX",
"@A@A@A@A@A@A@A@A@A@A@A@A@A@A@A@A@ABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXY",
"ABABABABABABABABABABABABABABABABABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZ",
"BABABABABABABABABABABABABABABABABABCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZY",
"CBCBCBCBCBCBCBCBCBCBCBCBCBCBCBCBCBCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ",
"BCBCBCBCBCBCBCBCBCBCBCBCBCBCBCBCBCBCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[",
"CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z",
"DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[",
"EDEDEDEDEDEDEDEDEDEDEDEDEDEDEDEDEDEDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\",
"DEDEDEDEDEDEDEDEDEDEDEDEDEDEDEDEDEDEDEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[",
"EFEFEFEFEFEFEFEFEFEFEFEFEFEFEFEFEFEFEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\",
"FEFEFEFEFEFEFEFEFEFEFEFEFEFEFEFEFEFEFEFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]",
"GFGFGFGFGFGFGFGFGFGFGFGFGFGFGFGFGFGFGFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\",
"FGFGFGFGFGFGFGFGFGFGFGFGFGFGFGFGFGFGFGFGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]",
"GHGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^",
"HGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]",
"IHIHIHIHIHIHIHIHIHIHIHIHIHIHIHIHIHIHIHIHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^",
"HIHIHIHIHIHIHIHIHIHIHIHIHIHIHIHIHIHIHIHIHIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_",
"IJIJIJIJIJIJIJIJIJIJIJIJIJIJIJIJIJIJIJIJIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^",
"JIJIJIJIJIJIJIJIJIJIJIJIJIJIJIJIJIJIJIJIJIJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_",
"KJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`",
"JKJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKJKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_",
"KLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`",
"LKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLKLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a",
"MLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`",
"LMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMLMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`a",
"MNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ab",
"NMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNMNONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`aba",
"ONONONONONONONONONONONONONONONONONONONONONONONONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`abab",
"NONONONONONONONONONONONONONONONONONONONONONONONOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ababc",
"OPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ababcb",
"POPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPOPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ababcbc",
"QPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ababcbcd",
"PQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ababcbcdc",
"QRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ababcbcdcd",
"RQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRQRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ababcbcdcde",
"SRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ababcbcdcded",
"RSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSRSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ababcbcdcdede",
"STSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ababcbcdcdedef",
"TSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTSTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ababcbcdcdedefe",
"UTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ababcbcdcdedefef",
"TUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUTUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ababcbcdcdedefefg",
"UVUVUVUVUVUVUVUVUVUVUVUVUVUVUVUVUVUVUVUVUVUVUVUVUVUVUVUVWVWXWXYXYZYZ[Z[\\[\\]\\]^]^_^_`_`a`ababcbcdcdedefefgf"
};