//the latest
//the latest
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Idone
{
{
int[][][] Box = new int[9][9][11] ; for(int i= 0; i<9;i++) {
for(int j= 0;j<9;j++) {
for(int k = 0; k<9;k++) {
}//for k
}//for j
}//for i
/*assign( Box ,0 ,2 ,5 );
assign( Box , 0, 5,1 );
assign( Box , 0, 7,8);
assign( Box , 0, 8,6 );
assign( Box , 1, 3,2 );
assign( Box , 1,8 ,3 );
assign( Box , 2, 0,3 );
assign( Box , 2, 4,7 );
assign( Box , 3, 1,1 );
assign( Box , 3,3 ,4 );
assign( Box , 3,5 ,6 );
assign( Box , 3, 8, 7);
assign( Box , 4, 2,3 );
assign( Box , 4, 6,5 );
assign( Box , 5,0 ,7 );
assign( Box , 5,3 ,1 );
assign( Box , 5,5 ,3 );
assign( Box , 5, 7, 4);
assign( Box , 6,4 ,6 );
assign( Box , 6,8 ,9 );
assign( Box , 7,0 ,2 );
assign( Box , 7,5 ,7 );
assign( Box , 8,0 ,5 );
assign( Box , 8,1 ,8 );
assign( Box , 8, 3, 9);
assign( Box , 8, 6, 2);*/
/*assign( Box ,0 ,0 ,3 );
assign( Box , 0, 1,7 );
assign( Box , 0, 3,5);
assign( Box , 0, 4,1 );
assign( Box , 0, 5,8 );
assign( Box , 1,8 ,9 );
assign( Box , 2, 1,6 );
assign( Box , 2, 2,4 );
assign( Box , 2, 3,9 );
assign( Box , 2,6 ,8 );
assign( Box , 3,0 ,1 );
assign( Box , 3, 4, 5);
assign( Box , 3, 8,4 );
assign( Box , 4, 2,2 );
assign( Box , 4,6 ,7 );
assign( Box , 5,0 ,9 );
assign( Box , 5,4 ,3 );
assign( Box , 5, 8, 2);
assign( Box , 6,2 ,3 );
assign( Box , 6,5 ,7 );
assign( Box , 6,6 ,9 );
assign( Box , 6,7 ,5 );
assign( Box , 7,0 ,4 );
assign( Box , 8,3 ,8 );
assign( Box , 8, 4, 2);
assign( Box , 8, 5, 6);
assign( Box ,8,7,4);
assign( Box ,8,8,3);*/
/*
//Ozone
assign( Box ,0 ,1 ,7 );
assign( Box , 0, 3,9 );
assign( Box , 1, 2,3 );
assign( Box , 1, 4,4 );
assign( Box , 1, 8,7 );
assign( Box , 2,2 ,2 );
assign( Box , 2, 4,7 );
assign( Box , 2, 5,1 );
assign( Box , 2, 6,8 );
assign( Box , 2,7 ,6 );
assign( Box , 3,2 ,6 );
assign( Box , 3, 8, 4);
assign( Box , 4, 1,5 );
assign( Box , 4, 2,4 );
assign( Box , 4,4 ,8 );
assign( Box , 4,6 ,9 );
assign( Box , 4,7 ,3 );
assign( Box , 5, 0, 3);
assign( Box , 5,6 ,7 );
assign( Box , 6,1 ,3 );
assign( Box , 6,2 ,7 );
assign( Box , 6,3 ,6 );
assign( Box , 6,4 ,2 );
assign( Box , 6,6 ,1 );
assign( Box , 7, 0, 9);
assign( Box , 7, 4, 5);
assign( Box ,7,6,6);
assign( Box ,8,5,7);
assign( Box ,8,7,2);*/
/*assign( Box ,0 ,5 ,3 );
assign( Box , 0, 6,5 );
assign( Box , 0, 7,1 );
assign( Box , 0, 8,4 );
assign( Box , 1, 3,4 );
assign( Box , 1,8 ,8 );
assign( Box , 2, 3,6 );
assign( Box , 2, 4,7 );
assign( Box , 2, 8,2 );
assign( Box , 3,1 ,8 );
assign( Box , 3,2 ,1 );
assign( Box , 3, 8, 5);
assign( Box , 4, 2,3 );
assign( Box , 4, 6,2 );
assign( Box , 5,0 ,2 );
assign( Box , 5,6 ,9 );
assign( Box , 5,7 ,6 );
assign( Box , 6, 0, 5);
assign( Box , 6,4 ,1 );
assign( Box , 6,5 ,9 );
assign( Box , 7,0 ,9 );
assign( Box , 7,5 ,7 );
assign( Box , 8,0 ,1 );
assign( Box , 8,1 ,7 );
assign( Box , 8, 2, 6);
assign( Box , 8, 3, 5);*/
/*assign( Box ,0 ,2,6 );
assign( Box , 0,4 ,1 );
assign( Box , 0,6 ,8 );
assign( Box , 0,8 ,3 );
assign( Box , 1,1 ,7 );
assign( Box , 1,4 ,2 );
assign( Box , 2,0 ,8 );
assign( Box , 2,5 ,4 );
assign( Box , 2,8 ,5 );
assign( Box , 3,3 ,5 );
assign( Box , 3,6 ,4 );
assign( Box , 4,0 ,5 );
assign( Box , 4,1 ,4 );
assign( Box , 4,7 ,3 );
assign( Box ,4 ,8 ,2 );
assign( Box , 5,2 ,7 );
assign( Box , 5,5 ,8 );
assign( Box , 6,0 ,6 );
assign( Box , 6,3 ,7 );
assign( Box , 6, 8,1 );
assign( Box , 7, 4,8 );
assign( Box , 7, 7,9 );
assign( Box , 8, 0,2 );
assign( Box , 8, 2, 4);
assign( Box , 8, 4,5 );
assign( Box ,8 , 6,6 );*/
/*assign(Box,0,1,1);
assign(Box,0,2,8);
assign(Box,0,5,4);
assign(Box,0,6,3);
assign(Box,1,0,3);
assign(Box,1,5,5);
assign(Box,1,6,4);
assign(Box,2,0,7);
assign(Box,2,4,2);
assign(Box,2,7,8);
assign(Box,2,8,1);
assign(Box,3,7,5);
assign(Box,3,8,4);
assign(Box,4,2,4);
assign(Box,4,6,9);
assign(Box,5,0,8);
assign(Box,5,1,5);
assign(Box,6,0,2);
assign(Box,6,1,7);
assign(Box,6,4,9);
assign(Box,6,8,3);
assign(Box,7,2,1);
assign(Box,7,3,8);
assign(Box,7,8,7);
assign(Box,8,2,9);
assign(Box,8,3,7);
assign(Box,8,6,5);
assign(Box,8,7,1);
*/
for (int i = 0 ; i < 10; i++){
}
//is_solved(Box);
System.
out.
println("_______________"); for (int i = 0 ; i <9; i++){
print_possibilities_of_specific_value
(Box,
7);//print_possibilities_of_specific_square(Box,0,0);
print_possibilities_of_each_square
(Box);}
/////is_unique(Box);
//System.out.println("_______________");
//print_big_box(Box);
}
public static void print_possibilities_of_each_square(int[][][] B_Box){
// print the possibility of a certain square
// System.out.println(check_same_big_box(B_Box,1,5,1));
for(int i = 0; i<9 ; i++){
if (i%3==0){
System.
out.
println("____________________"); }
for(int j = 0;j<9 ; j++){
if (j%3==0){
}
System.
out.
print(B_Box
[i
][j
][10]+ " "); }
}
}
public static void print_possibilities_of_specific_value(int[][][] B_Box, int v ){
// print the possibility of a certain square
// System.out.println(check_same_big_box(B_Box,1,5,1));
for(int i = 0; i<9 ; i++){
if (i%3==0){
System.
out.
println("____________________"); }
for(int j = 0;j<9 ; j++){
if (j%3==0){
}
System.
out.
print(B_Box
[i
][j
][v
-1]+ " "); }
}
}
public static void print_possibilities_of_specific_square(int[][][] B_Box, int r, int c){
// print the possibility of a certain square
for(int i = 0; i<9 ; i++){
System.
out.
print(B_Box
[r
][c
][i
]+ " ");
}
}
public static void print_big_box(int[][][] B_Box){
for(int i = 0; i<9 ; i++){
for(int j = 0; j<9 ; j++){
System.
out.
print(B_Box
[i
][j
][9] + " "); }//for j
}//for i
}//print_big_box()
public static void change_marks_same_big_box(int[][][] B_Box, int r,int c, int val) {
for(int i = r - r%3; i<3+(r - r%3) ; i++){
for(int j = c - c%3; j<3+(c - c%3) ; j++){
if ( (B_Box[i][j][9] == 0) && ( B_Box[i][j][10]>1) && (B_Box[i][j][val-1]==1)){
B_Box[i][j][val-1]=0;
B_Box[i][j][10]--;
/* if( B_Box[i][j][10]==1){
for (int a = 0 ; a < 9 ; a++) {
if ( B_Box[i][j][a]==1) {
assign(B_Box,i,j,a+1);
}//if
}//for a
}*///if
//check_small_square_in_big_square(BBBox,b_b,i);
}//if
}//for j
}//for i
}//change_marks_same_big_box
public static void change_marks_same_row(int[][][] B_Box, int r,int c, int val) {
for(int j = 0; j<9 ; j++){
if ( (B_Box[r][j][9] == 0) && ( B_Box[r][j][10]>1)&& (B_Box[r][j][val-1]==1)){
B_Box[r][j][val-1]=0;
B_Box[r][j][10]--;
/* if( B_Box[r][j][10]==1){
for (int a = 0 ; a < 9 ; a++) {
if ( B_Box[r][j][a]==1) {
assign(B_Box,r,j,a+1);
}//if
}//for a
}*///if
//check_small_square_in_big_square(BBBox,b_b,i);
}//if
}//for j
}//change_marks_same_row
public static void change_marks_same_column(int[][][] B_Box, int r,int c, int val) {
for(int i = 0; i<9 ; i++){
if ( (B_Box[i][c][9] == 0) && ( B_Box[i][c][10]>1)&& (B_Box[i][c][val-1]==1)){
B_Box[i][c][val-1]=0;
B_Box[i][c][10]--;
/* if( B_Box[i][c][10]==1){
for (int a = 0 ; a < 9 ; a++) {
if ( B_Box[i][c][a]==1) {
assign(B_Box,i,c,a+1);
}//if
}//for a
}*/
//if
//check_small_square_in_big_square(BBBox,b_b,i);
}//if
}//for j
}//change_marks_same_column
public static int check_same_big_box(int[][][] B_Box, int r,int c, int val) {
int cnts=0;
int cntr=0;
int cntc=0;
int cnt=0;
int x=-1;
int y=-1;
int u=-1;
int v=-1;
for(int i = r - r%3; i<3+(r - r%3) ; i++){
for(int j = c - c%3; j<3+(c - c%3) ; j++){
if ( (B_Box[i][j][9] == 0) &&(B_Box[i][j][val-1]==1)&&(B_Box[r][c][val-1]==1)){
cnts++;
// if((i==0)&&(j==3) &&(val==3))
// {System.out.println("hiiiii cnts: " + cnts + "r: "+i +"col: "+j );
// }
if(cnts==1){
x=i;
y=j;
}
if(cnts==2){
u=i;
v=j;
}
}//if
}//for j
}//for i
if(cnts>0){
for(int i = 0; i<9;i++){
if ( (B_Box[i][c][9] == 0) &&(B_Box[i][c][val-1]==1)&&(B_Box[r][c][val-1]==1)){
cntc++;
}//if
}//for i
if (cntc>0){
for(int j = 0;j<9;j++){
if ( (B_Box[r][j][9] == 0) &&(B_Box[r][j][val-1]==1)&&(B_Box[r][c][val-1]==1)){
cntr++;
}//if
}//for i
}//if cntc
}//if
if(cnts==2){
//System.out.println("hiiiiiiiiiiiii");
if(y==v){
for(int i=0;i<9;i++){
if((i!=x)&&(i!=u)&&(B_Box[i][y][val-1]==1)){
// if((i==0)&&(y==3) &&(val==3))
// {System.out.println("hiiiiiMarcel" + cnts);
// }
B_Box[i][y][val-1]=0;
B_Box[i][y][10]--;
}
}
}
if(x==u){
for(int i=0;i<9;i++){
if((i!=y)&&(i!=v)&&(B_Box[x][i][val-1]==1)){
B_Box[x][i][val-1]=0;
B_Box[x][i][10]--;
}
}
}
}
// if((r==0)&&(c==3) &&(val==3))
//// {
//System.out.println("cnts: "+ cnts + " cntc: "+ cntc+" cntr: "+ cntr);
//}
if ((cnts==1)||(cntc==1)||(cntr==1)){
cnt=1;
}
return cnt;
}//check_same_big_box
public static void is_unique(int[][][] B_Box) {
for(int m = 0; m<9 ; m++){
for(int n = 0; n<9 ; n++){
// if((m==0)&&(n==3)){
// System.out.println("check_same_big_box("+m+","+n+","+6+")" +B_Box[m][n][10]+" "+B_Box[m][n][9] + " "+check_same_big_box(B_Box,m,n,3));
// }//if
if((B_Box[m][n][9] == 0) && ( B_Box[m][n][10]>1)){
for (int a = 1 ; a < 10 ; a++) {
if(check_same_big_box(B_Box,m,n,a)==1){
assign(B_Box,m,n,a);
}//if
}//for a
}//if
if((B_Box[m][n][9] == 0) && ( B_Box[m][n][10]==1)){
for (int a = 1 ; a < 10 ; a++) {
if(B_Box[m][n][a-1]==1){
assign(B_Box,m,n,a);
}//if
}//for a
}//if
}//for j
}//for //i
}
public static void is_solved(int[][][] B_Box) {
for(int i = 0; i<9 ; i++){
for(int j = 0; j<9 ; j++){
if((B_Box[i][j][9] == 0) && ( B_Box[i][j][10]==1)){
for (int a = 0 ; a < 9 ; a++) {
if ( B_Box[i][j][a]==1) {
assign(B_Box,i,j,a+1);
}//if
}//fora
}//if
}//forj
}//for i
}
public static void assign(int[][][] B_Box, int r,int c, int val) {
B_Box[r][c][9]= val;
B_Box[r][c][10]=1;
B_Box[r][c][val-1]=1;
for (int i = 0; i < 9; i++){
if(i!=(val-1)){
B_Box[r][c][i]=0;
}//if
}//for i
change_marks_same_big_box(B_Box,r,c,val);
change_marks_same_row(B_Box,r,c,val);
change_marks_same_column(B_Box,r,c,val);
is_unique(B_Box);
//is_solved(BBBox);
}
}
Ly90aGUgbGF0ZXN0Ci8vdGhlIGxhdGVzdAovKiBwYWNrYWdlIHdoYXRldmVyOyAvLyBkb24ndCBwbGFjZSBwYWNrYWdlIG5hbWUhICovCmltcG9ydCBqYXZhLnV0aWwuKjsKaW1wb3J0IGphdmEubGFuZy4qOwppbXBvcnQgamF2YS5pby4qOwoKCgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KIGNsYXNzIElkb25lCnsKcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBqYXZhLmxhbmcuRXhjZXB0aW9uCnsKaW50W11bXVtdICBCb3ggPSBuZXcgaW50WzldWzldWzExXSA7CmZvcihpbnQgaT0gMDsgaTw5O2krKykgewpmb3IoaW50IGo9IDA7ajw5O2orKykgewpCb3hbaV1bal1bOV09MDsKQm94W2ldW2pdWzEwXT05Owpmb3IoaW50IGsgPSAwOyBrPDk7aysrKSB7CkJveFtpXVtqXVtrXSA9IDE7Cn0vL2ZvciBrCn0vL2ZvciBqCn0vL2ZvciBpCi8qYXNzaWduKCBCb3ggLDAgLDIgLDUgKTsKYXNzaWduKCBCb3ggLCAwLCA1LDEgKTsKYXNzaWduKCBCb3ggLCAwLCA3LDgpOwphc3NpZ24oIEJveCAsIDAsIDgsNiApOwphc3NpZ24oIEJveCAsIDEsIDMsMiApOwphc3NpZ24oIEJveCAsIDEsOCAsMyApOwphc3NpZ24oIEJveCAsIDIsIDAsMyApOwphc3NpZ24oIEJveCAsIDIsIDQsNyApOwphc3NpZ24oIEJveCAsIDMsIDEsMSApOwphc3NpZ24oIEJveCAsIDMsMyAsNCApOwphc3NpZ24oIEJveCAsIDMsNSAsNiApOwphc3NpZ24oIEJveCAsIDMsIDgsIDcpOwphc3NpZ24oIEJveCAsIDQsIDIsMyApOwphc3NpZ24oIEJveCAsIDQsIDYsNSApOwphc3NpZ24oIEJveCAsIDUsMCAsNyApOwphc3NpZ24oIEJveCAsIDUsMyAsMSApOwphc3NpZ24oIEJveCAsIDUsNSAsMyApOwphc3NpZ24oIEJveCAsIDUsIDcsIDQpOwphc3NpZ24oIEJveCAsIDYsNCAsNiApOwphc3NpZ24oIEJveCAsIDYsOCAsOSApOwphc3NpZ24oIEJveCAsIDcsMCAsMiApOwphc3NpZ24oIEJveCAsIDcsNSAsNyApOwphc3NpZ24oIEJveCAsIDgsMCAsNSApOwphc3NpZ24oIEJveCAsIDgsMSAsOCApOwphc3NpZ24oIEJveCAsIDgsIDMsIDkpOwphc3NpZ24oIEJveCAsIDgsIDYsIDIpOyovCgovKmFzc2lnbiggQm94ICwwICwwICwzICk7CmFzc2lnbiggQm94ICwgMCwgMSw3ICk7CmFzc2lnbiggQm94ICwgMCwgMyw1KTsKYXNzaWduKCBCb3ggLCAwLCA0LDEgKTsKYXNzaWduKCBCb3ggLCAwLCA1LDggKTsKYXNzaWduKCBCb3ggLCAxLDggLDkgKTsKYXNzaWduKCBCb3ggLCAyLCAxLDYgKTsKYXNzaWduKCBCb3ggLCAyLCAyLDQgKTsKYXNzaWduKCBCb3ggLCAyLCAzLDkgKTsKYXNzaWduKCBCb3ggLCAyLDYgLDggKTsKYXNzaWduKCBCb3ggLCAzLDAgLDEgKTsKYXNzaWduKCBCb3ggLCAzLCA0LCA1KTsKYXNzaWduKCBCb3ggLCAzLCA4LDQgKTsKYXNzaWduKCBCb3ggLCA0LCAyLDIgKTsKYXNzaWduKCBCb3ggLCA0LDYgLDcgKTsKYXNzaWduKCBCb3ggLCA1LDAgLDkgKTsKYXNzaWduKCBCb3ggLCA1LDQgLDMgKTsKYXNzaWduKCBCb3ggLCA1LCA4LCAyKTsKYXNzaWduKCBCb3ggLCA2LDIgLDMgKTsKYXNzaWduKCBCb3ggLCA2LDUgLDcgKTsKYXNzaWduKCBCb3ggLCA2LDYgLDkgKTsKYXNzaWduKCBCb3ggLCA2LDcgLDUgKTsKYXNzaWduKCBCb3ggLCA3LDAgLDQgKTsKYXNzaWduKCBCb3ggLCA4LDMgLDggKTsKYXNzaWduKCBCb3ggLCA4LCA0LCAyKTsKYXNzaWduKCBCb3ggLCA4LCA1LCA2KTsKYXNzaWduKCBCb3ggLDgsNyw0KTsKYXNzaWduKCBCb3ggLDgsOCwzKTsqLwovKgovL096b25lCmFzc2lnbiggQm94ICwwICwxICw3ICk7CmFzc2lnbiggQm94ICwgMCwgMyw5ICk7CmFzc2lnbiggQm94ICwgMSwgMiwzICk7CmFzc2lnbiggQm94ICwgMSwgNCw0ICk7CmFzc2lnbiggQm94ICwgMSwgOCw3ICk7CmFzc2lnbiggQm94ICwgMiwyICwyICk7CmFzc2lnbiggQm94ICwgMiwgNCw3ICk7CmFzc2lnbiggQm94ICwgMiwgNSwxICk7CmFzc2lnbiggQm94ICwgMiwgNiw4ICk7CmFzc2lnbiggQm94ICwgMiw3ICw2ICk7CmFzc2lnbiggQm94ICwgMywyICw2ICk7CmFzc2lnbiggQm94ICwgMywgOCwgNCk7CmFzc2lnbiggQm94ICwgNCwgMSw1ICk7CmFzc2lnbiggQm94ICwgNCwgMiw0ICk7CmFzc2lnbiggQm94ICwgNCw0ICw4ICk7CmFzc2lnbiggQm94ICwgNCw2ICw5ICk7CmFzc2lnbiggQm94ICwgNCw3ICwzICk7CmFzc2lnbiggQm94ICwgNSwgMCwgMyk7CmFzc2lnbiggQm94ICwgNSw2ICw3ICk7CmFzc2lnbiggQm94ICwgNiwxICwzICk7CmFzc2lnbiggQm94ICwgNiwyICw3ICk7CmFzc2lnbiggQm94ICwgNiwzICw2ICk7CmFzc2lnbiggQm94ICwgNiw0ICwyICk7CmFzc2lnbiggQm94ICwgNiw2ICwxICk7CmFzc2lnbiggQm94ICwgNywgMCwgOSk7CmFzc2lnbiggQm94ICwgNywgNCwgNSk7CmFzc2lnbiggQm94ICw3LDYsNik7CmFzc2lnbiggQm94ICw4LDUsNyk7CmFzc2lnbiggQm94ICw4LDcsMik7Ki8KCi8qYXNzaWduKCBCb3ggLDAgLDUgLDMgKTsKYXNzaWduKCBCb3ggLCAwLCA2LDUgKTsKYXNzaWduKCBCb3ggLCAwLCA3LDEgKTsKYXNzaWduKCBCb3ggLCAwLCA4LDQgKTsKYXNzaWduKCBCb3ggLCAxLCAzLDQgKTsKYXNzaWduKCBCb3ggLCAxLDggLDggKTsKYXNzaWduKCBCb3ggLCAyLCAzLDYgKTsKYXNzaWduKCBCb3ggLCAyLCA0LDcgKTsKYXNzaWduKCBCb3ggLCAyLCA4LDIgKTsKYXNzaWduKCBCb3ggLCAzLDEgLDggKTsKYXNzaWduKCBCb3ggLCAzLDIgLDEgKTsKYXNzaWduKCBCb3ggLCAzLCA4LCA1KTsKYXNzaWduKCBCb3ggLCA0LCAyLDMgKTsKYXNzaWduKCBCb3ggLCA0LCA2LDIgKTsKYXNzaWduKCBCb3ggLCA1LDAgLDIgKTsKYXNzaWduKCBCb3ggLCA1LDYgLDkgKTsKYXNzaWduKCBCb3ggLCA1LDcgLDYgKTsKYXNzaWduKCBCb3ggLCA2LCAwLCA1KTsKYXNzaWduKCBCb3ggLCA2LDQgLDEgKTsKYXNzaWduKCBCb3ggLCA2LDUgLDkgKTsKYXNzaWduKCBCb3ggLCA3LDAgLDkgKTsKYXNzaWduKCBCb3ggLCA3LDUgLDcgKTsKYXNzaWduKCBCb3ggLCA4LDAgLDEgKTsKYXNzaWduKCBCb3ggLCA4LDEgLDcgKTsKYXNzaWduKCBCb3ggLCA4LCAyLCA2KTsKYXNzaWduKCBCb3ggLCA4LCAzLCA1KTsqLwoKLyphc3NpZ24oIEJveCAsMCAsMiw2ICk7CmFzc2lnbiggQm94ICwgMCw0ICwxICk7CmFzc2lnbiggQm94ICwgMCw2ICw4ICk7CmFzc2lnbiggQm94ICwgMCw4ICwzICk7CmFzc2lnbiggQm94ICwgMSwxICw3ICk7CmFzc2lnbiggQm94ICwgMSw0ICwyICk7CmFzc2lnbiggQm94ICwgMiwwICw4ICk7CmFzc2lnbiggQm94ICwgMiw1ICw0ICk7CmFzc2lnbiggQm94ICwgMiw4ICw1ICk7CmFzc2lnbiggQm94ICwgMywzICw1ICk7CmFzc2lnbiggQm94ICwgMyw2ICw0ICk7CmFzc2lnbiggQm94ICwgNCwwICw1ICk7CmFzc2lnbiggQm94ICwgNCwxICw0ICk7CmFzc2lnbiggQm94ICwgNCw3ICwzICk7CmFzc2lnbiggQm94ICw0ICw4ICwyICk7CmFzc2lnbiggQm94ICwgNSwyICw3ICk7CmFzc2lnbiggQm94ICwgNSw1ICw4ICk7CmFzc2lnbiggQm94ICwgNiwwICw2ICk7CmFzc2lnbiggQm94ICwgNiwzICw3ICk7CmFzc2lnbiggQm94ICwgNiwgOCwxICk7CmFzc2lnbiggQm94ICwgNywgNCw4ICk7CmFzc2lnbiggQm94ICwgNywgNyw5ICk7CmFzc2lnbiggQm94ICwgOCwgMCwyICk7CmFzc2lnbiggQm94ICwgOCwgMiwgNCk7CmFzc2lnbiggQm94ICwgOCwgNCw1ICk7CmFzc2lnbiggQm94ICw4ICwgNiw2ICk7Ki8KCmFzc2lnbihCb3gsMCwzLDQpOwphc3NpZ24oQm94LDAsNCw4KTsKYXNzaWduKEJveCwwLDYsNik7CmFzc2lnbihCb3gsMCw3LDIpOwphc3NpZ24oQm94LDEsNCwyKTsKYXNzaWduKEJveCwxLDgsOSk7CmFzc2lnbihCb3gsMiwyLDMpOwphc3NpZ24oQm94LDIsNSw3KTsKYXNzaWduKEJveCwyLDgsNSk7CmFzc2lnbihCb3gsMywwLDkpOwphc3NpZ24oQm94LDMsNSw4KTsKYXNzaWduKEJveCwzLDYsNSk7CmFzc2lnbihCb3gsNCw4LDcpOwphc3NpZ24oQm94LDQsMCwxKTsKYXNzaWduKEJveCw0LDEsNCk7CmFzc2lnbihCb3gsNCw3LDgpOwphc3NpZ24oQm94LDUsMiw3KTsKYXNzaWduKEJveCw1LDMsMik7CmFzc2lnbihCb3gsNSw4LDEpOwphc3NpZ24oQm94LDYsMCwyKTsKYXNzaWduKEJveCw2LDMsOCk7CmFzc2lnbihCb3gsNiw2LDMpOwphc3NpZ24oQm94LDcsMCw0KTsKYXNzaWduKEJveCw3LDQsNik7CmFzc2lnbihCb3gsOCwxLDkpOwphc3NpZ24oQm94LDgsMiw4KTsKYXNzaWduKEJveCw4LDQsNSk7CmFzc2lnbihCb3gsOCw1LDQpOwoKLyphc3NpZ24oQm94LDAsMSwxKTsKYXNzaWduKEJveCwwLDIsOCk7CmFzc2lnbihCb3gsMCw1LDQpOwphc3NpZ24oQm94LDAsNiwzKTsKYXNzaWduKEJveCwxLDAsMyk7CmFzc2lnbihCb3gsMSw1LDUpOwphc3NpZ24oQm94LDEsNiw0KTsKYXNzaWduKEJveCwyLDAsNyk7CmFzc2lnbihCb3gsMiw0LDIpOwphc3NpZ24oQm94LDIsNyw4KTsKYXNzaWduKEJveCwyLDgsMSk7CmFzc2lnbihCb3gsMyw3LDUpOwphc3NpZ24oQm94LDMsOCw0KTsKYXNzaWduKEJveCw0LDIsNCk7CmFzc2lnbihCb3gsNCw2LDkpOwphc3NpZ24oQm94LDUsMCw4KTsKYXNzaWduKEJveCw1LDEsNSk7CmFzc2lnbihCb3gsNiwwLDIpOwphc3NpZ24oQm94LDYsMSw3KTsKYXNzaWduKEJveCw2LDQsOSk7CmFzc2lnbihCb3gsNiw4LDMpOwphc3NpZ24oQm94LDcsMiwxKTsKYXNzaWduKEJveCw3LDMsOCk7CmFzc2lnbihCb3gsNyw4LDcpOwphc3NpZ24oQm94LDgsMiw5KTsKYXNzaWduKEJveCw4LDMsNyk7CmFzc2lnbihCb3gsOCw2LDUpOwphc3NpZ24oQm94LDgsNywxKTsKKi8KZm9yIChpbnQgaSA9IDAgOyBpIDwgMTA7IGkrKyl7CmlzX3VuaXF1ZShCb3gpOwp9CnByaW50X2JpZ19ib3goQm94KTsKLy9pc19zb2x2ZWQoQm94KTsKU3lzdGVtLm91dC5wcmludGxuKCJfX19fX19fX19fX19fX18iKTsKZm9yIChpbnQgaSA9IDAgOyBpIDw5OyBpKyspewpwcmludF9wb3NzaWJpbGl0aWVzX29mX3NwZWNpZmljX3ZhbHVlKEJveCw3KTsKLy9wcmludF9wb3NzaWJpbGl0aWVzX29mX3NwZWNpZmljX3NxdWFyZShCb3gsMCwwKTsKcHJpbnRfcG9zc2liaWxpdGllc19vZl9lYWNoX3NxdWFyZShCb3gpOwp9Ci8vLy8vaXNfdW5pcXVlKEJveCk7Ci8vU3lzdGVtLm91dC5wcmludGxuKCJfX19fX19fX19fX19fX18iKTsKLy9wcmludF9iaWdfYm94KEJveCk7Cn0KcHVibGljIHN0YXRpYyB2b2lkIHByaW50X3Bvc3NpYmlsaXRpZXNfb2ZfZWFjaF9zcXVhcmUoaW50W11bXVtdIEJfQm94KXsKCS8vIHByaW50IHRoZSBwb3NzaWJpbGl0eSBvZiBhIGNlcnRhaW4gc3F1YXJlCgkvLwlTeXN0ZW0ub3V0LnByaW50bG4oY2hlY2tfc2FtZV9iaWdfYm94KEJfQm94LDEsNSwxKSk7Cgpmb3IoaW50IGkgPSAwOyBpPDkgOyBpKyspewoJCWlmIChpJTM9PTApewoJCQlTeXN0ZW0ub3V0LnByaW50bG4oIl9fX19fX19fX19fX19fX19fX19fIik7Cgl9Cglmb3IoaW50IGogPSAwO2o8OSA7IGorKyl7CglpZiAoaiUzPT0wKXsKCQkJU3lzdGVtLm91dC5wcmludCgifCIpOwoJfQoJU3lzdGVtLm91dC5wcmludChCX0JveFtpXVtqXVsxMF0rICIgIik7Cgl9CglTeXN0ZW0ub3V0LnByaW50bG4oKTsKCgkKfQpTeXN0ZW0ub3V0LnByaW50bG4oKTsKfQpwdWJsaWMgc3RhdGljIHZvaWQgcHJpbnRfcG9zc2liaWxpdGllc19vZl9zcGVjaWZpY192YWx1ZShpbnRbXVtdW10gQl9Cb3gsIGludCB2ICl7CgkvLyBwcmludCB0aGUgcG9zc2liaWxpdHkgb2YgYSBjZXJ0YWluIHNxdWFyZQoJLy8JU3lzdGVtLm91dC5wcmludGxuKGNoZWNrX3NhbWVfYmlnX2JveChCX0JveCwxLDUsMSkpOwoKZm9yKGludCBpID0gMDsgaTw5IDsgaSsrKXsKCQlpZiAoaSUzPT0wKXsKCQkJU3lzdGVtLm91dC5wcmludGxuKCJfX19fX19fX19fX19fX19fX19fXyIpOwoJfQoJZm9yKGludCBqID0gMDtqPDkgOyBqKyspewoJaWYgKGolMz09MCl7CgkJCVN5c3RlbS5vdXQucHJpbnQoInwiKTsKCX0KCVN5c3RlbS5vdXQucHJpbnQoQl9Cb3hbaV1bal1bdi0xXSsgIiAiKTsKCX0KCVN5c3RlbS5vdXQucHJpbnRsbigpOwoKCQp9ClN5c3RlbS5vdXQucHJpbnRsbigpOwp9CnB1YmxpYyBzdGF0aWMgdm9pZCBwcmludF9wb3NzaWJpbGl0aWVzX29mX3NwZWNpZmljX3NxdWFyZShpbnRbXVtdW10gQl9Cb3gsIGludCByLCBpbnQgYyl7CgkvLyBwcmludCB0aGUgcG9zc2liaWxpdHkgb2YgYSBjZXJ0YWluIHNxdWFyZQoKZm9yKGludCBpID0gMDsgaTw5IDsgaSsrKXsKCVN5c3RlbS5vdXQucHJpbnQoQl9Cb3hbcl1bY11baV0rICIgIik7CgkKfQpTeXN0ZW0ub3V0LnByaW50bG4oKTsKfQpwdWJsaWMgc3RhdGljIHZvaWQgcHJpbnRfYmlnX2JveChpbnRbXVtdW10gIEJfQm94KXsKCmZvcihpbnQgaSA9IDA7IGk8OSA7IGkrKyl7CmZvcihpbnQgaiA9IDA7IGo8OSA7IGorKyl7ClN5c3RlbS5vdXQucHJpbnQoQl9Cb3hbaV1bal1bOV0gKyAiICIpOwp9Ly9mb3IgagoKU3lzdGVtLm91dC5wcmludGxuKCk7Cn0vL2ZvciBpCn0vL3ByaW50X2JpZ19ib3goKQoKcHVibGljIHN0YXRpYyB2b2lkIGNoYW5nZV9tYXJrc19zYW1lX2JpZ19ib3goaW50W11bXVtdICBCX0JveCwgaW50IHIsaW50IGMsIGludCB2YWwpIHsKCQpmb3IoaW50IGkgPSByIC0gciUzOyBpPDMrKHIgLSByJTMpIDsgaSsrKXsKZm9yKGludCBqID0gYyAtIGMlMzsgajwzKyhjIC0gYyUzKSA7IGorKyl7CgppZiAoIChCX0JveFtpXVtqXVs5XSA9PSAwKSAmJiAoIEJfQm94W2ldW2pdWzEwXT4xKSAmJiAoQl9Cb3hbaV1bal1bdmFsLTFdPT0xKSl7CglCX0JveFtpXVtqXVt2YWwtMV09MDsKCUJfQm94W2ldW2pdWzEwXS0tOwovKglpZiggQl9Cb3hbaV1bal1bMTBdPT0xKXsKCQlmb3IgKGludCBhID0gMCA7IGEgPCA5IDsgYSsrKQl7CgkJaWYgKCBCX0JveFtpXVtqXVthXT09MSkJewoJCgkJYXNzaWduKEJfQm94LGksaixhKzEpOwoJfS8vaWYKCX0vL2ZvciBhCgl9Ki8vL2lmCgkvL2NoZWNrX3NtYWxsX3NxdWFyZV9pbl9iaWdfc3F1YXJlKEJCQm94LGJfYixpKTsKCn0vL2lmCn0vL2ZvciBqCn0vL2ZvciBpCQp9Ly9jaGFuZ2VfbWFya3Nfc2FtZV9iaWdfYm94CgpwdWJsaWMgc3RhdGljIHZvaWQgY2hhbmdlX21hcmtzX3NhbWVfcm93KGludFtdW11bXSAgQl9Cb3gsIGludCByLGludCBjLCBpbnQgdmFsKSB7CgkKCmZvcihpbnQgaiA9IDA7IGo8OSA7IGorKyl7CgppZiAoIChCX0JveFtyXVtqXVs5XSA9PSAwKSAmJiAoIEJfQm94W3JdW2pdWzEwXT4xKSYmIChCX0JveFtyXVtqXVt2YWwtMV09PTEpKXsKCUJfQm94W3JdW2pdW3ZhbC0xXT0wOwoJQl9Cb3hbcl1bal1bMTBdLS07Ci8qCWlmKCBCX0JveFtyXVtqXVsxMF09PTEpewoJCWZvciAoaW50IGEgPSAwIDsgYSA8IDkgOyBhKyspCXsKCQlpZiAoIEJfQm94W3JdW2pdW2FdPT0xKQl7CgkKCQlhc3NpZ24oQl9Cb3gscixqLGErMSk7Cgl9Ly9pZgoJfS8vZm9yIGEKCX0qLy8vaWYKCS8vY2hlY2tfc21hbGxfc3F1YXJlX2luX2JpZ19zcXVhcmUoQkJCb3gsYl9iLGkpOwoKfS8vaWYKfS8vZm9yIGoKCQp9Ly9jaGFuZ2VfbWFya3Nfc2FtZV9yb3cKCnB1YmxpYyBzdGF0aWMgdm9pZCBjaGFuZ2VfbWFya3Nfc2FtZV9jb2x1bW4oaW50W11bXVtdICBCX0JveCwgaW50IHIsaW50IGMsIGludCB2YWwpIHsKCQoKZm9yKGludCBpID0gMDsgaTw5IDsgaSsrKXsKCmlmICggKEJfQm94W2ldW2NdWzldID09IDApICYmICggQl9Cb3hbaV1bY11bMTBdPjEpJiYgKEJfQm94W2ldW2NdW3ZhbC0xXT09MSkpewoJQl9Cb3hbaV1bY11bdmFsLTFdPTA7CglCX0JveFtpXVtjXVsxMF0tLTsKLyoJaWYoIEJfQm94W2ldW2NdWzEwXT09MSl7Cglmb3IgKGludCBhID0gMCA7IGEgPCA5IDsgYSsrKQl7CglpZiAoIEJfQm94W2ldW2NdW2FdPT0xKQl7CgoJIGFzc2lnbihCX0JveCxpLGMsYSsxKTsKCX0vL2lmCgl9Ly9mb3IgYQoJfSovCgkvL2lmCgkvL2NoZWNrX3NtYWxsX3NxdWFyZV9pbl9iaWdfc3F1YXJlKEJCQm94LGJfYixpKTsKCn0vL2lmCn0vL2ZvciBqCgkKfS8vY2hhbmdlX21hcmtzX3NhbWVfY29sdW1uCgpwdWJsaWMgc3RhdGljIGludCBjaGVja19zYW1lX2JpZ19ib3goaW50W11bXVtdICBCX0JveCwgaW50IHIsaW50IGMsIGludCB2YWwpIHsKaW50IGNudHM9MDsKaW50IGNudHI9MDsKaW50IGNudGM9MDsKaW50IGNudD0wOwppbnQgeD0tMTsKaW50IHk9LTE7CmludCB1PS0xOwppbnQgdj0tMTsKCmZvcihpbnQgaSA9IHIgLSByJTM7IGk8MysociAtIHIlMykgOyBpKyspewpmb3IoaW50IGogPSBjIC0gYyUzOyBqPDMrKGMgLSBjJTMpIDsgaisrKXsKCmlmICggKEJfQm94W2ldW2pdWzldID09IDApICYmKEJfQm94W2ldW2pdW3ZhbC0xXT09MSkmJihCX0JveFtyXVtjXVt2YWwtMV09PTEpKXsKCWNudHMrKzsKLy8JaWYoKGk9PTApJiYoaj09MykgJiYodmFsPT0zKSkKLy8Je1N5c3RlbS5vdXQucHJpbnRsbigiaGlpaWlpICBjbnRzOiAgIiArIGNudHMgKyAicjogIitpICsiY29sOiAiK2ogICk7Ci8vCX0KCWlmKGNudHM9PTEpewoJCXg9aTsKCQl5PWo7Cgl9CglpZihjbnRzPT0yKXsKCQl1PWk7CgkJdj1qOwoJfQoJCn0vL2lmCgp9Ly9mb3Igagp9Ly9mb3IgaQppZihjbnRzPjApewpmb3IoaW50IGkgPSAwOyBpPDk7aSsrKXsKaWYgKCAoQl9Cb3hbaV1bY11bOV0gPT0gMCkgJiYoQl9Cb3hbaV1bY11bdmFsLTFdPT0xKSYmKEJfQm94W3JdW2NdW3ZhbC0xXT09MSkpewoJY250YysrOwoJCn0vL2lmCQp9Ly9mb3IgaQoKaWYgKGNudGM+MCl7Cglmb3IoaW50IGogPSAwO2o8OTtqKyspewppZiAoIChCX0JveFtyXVtqXVs5XSA9PSAwKSAmJihCX0JveFtyXVtqXVt2YWwtMV09PTEpJiYoQl9Cb3hbcl1bY11bdmFsLTFdPT0xKSl7CgljbnRyKys7CgkKfS8vaWYJCn0vL2ZvciBpCn0vL2lmIGNudGMKCn0vL2lmCmlmKGNudHM9PTIpewoJLy9TeXN0ZW0ub3V0LnByaW50bG4oImhpaWlpaWlpaWlpaWlpIik7CglpZih5PT12KXsKCQlmb3IoaW50IGk9MDtpPDk7aSsrKXsKCQkJaWYoKGkhPXgpJiYoaSE9dSkmJihCX0JveFtpXVt5XVt2YWwtMV09PTEpKXsKCQkJCS8vCWlmKChpPT0wKSYmKHk9PTMpICYmKHZhbD09MykpCi8vCXtTeXN0ZW0ub3V0LnByaW50bG4oImhpaWlpaU1hcmNlbCIgKyBjbnRzKTsKLy8JfQoJCQlCX0JveFtpXVt5XVt2YWwtMV09MDsKCQkJQl9Cb3hbaV1beV1bMTBdLS07CgkJCX0KCQl9Cgl9CglpZih4PT11KXsKCQlmb3IoaW50IGk9MDtpPDk7aSsrKXsKCQkJaWYoKGkhPXkpJiYoaSE9dikmJihCX0JveFt4XVtpXVt2YWwtMV09PTEpKXsKCQkJQl9Cb3hbeF1baV1bdmFsLTFdPTA7CgkJCUJfQm94W3hdW2ldWzEwXS0tOwoJCQl9CgkJfQoJfQkKfQovLwlpZigocj09MCkmJihjPT0zKSAmJih2YWw9PTMpKQovLy8vCXsKLy9TeXN0ZW0ub3V0LnByaW50bG4oImNudHM6ICIrIGNudHMgKyAiIGNudGM6ICIrIGNudGMrIiBjbnRyOiAiKyBjbnRyKTsKLy99CmlmICgoY250cz09MSl8fChjbnRjPT0xKXx8KGNudHI9PTEpKXsKCWNudD0xOwp9CnJldHVybiBjbnQ7Cn0vL2NoZWNrX3NhbWVfYmlnX2JveAoKcHVibGljIHN0YXRpYyB2b2lkIGlzX3VuaXF1ZShpbnRbXVtdW10gIEJfQm94KSB7Cgpmb3IoaW50IG0gPSAwOyBtPDkgOyBtKyspewoJZm9yKGludCBuID0gMDsgbjw5IDsgbisrKXsKCQkvLwlpZigobT09MCkmJihuPT0zKSl7CgkvLwlTeXN0ZW0ub3V0LnByaW50bG4oImNoZWNrX3NhbWVfYmlnX2JveCgiK20rIiwiK24rIiwiKzYrIikiICtCX0JveFttXVtuXVsxMF0rIiAgICIrQl9Cb3hbbV1bbl1bOV0gKyAiICAiK2NoZWNrX3NhbWVfYmlnX2JveChCX0JveCxtLG4sMykpOwkKCQkvLwl9Ly9pZgoJCglpZigoQl9Cb3hbbV1bbl1bOV0gPT0gMCkgJiYgKCBCX0JveFttXVtuXVsxMF0+MSkpewoJCWZvciAoaW50IGEgPSAxIDsgYSA8IDEwIDsgYSsrKQl7CgkJCWlmKGNoZWNrX3NhbWVfYmlnX2JveChCX0JveCxtLG4sYSk9PTEpewoJCQoJCQkJYXNzaWduKEJfQm94LG0sbixhKTsKCQkKCQkJCgkJCX0vL2lmCgkJCX0vL2ZvciBhCgoJCX0vL2lmCgkJCWlmKChCX0JveFttXVtuXVs5XSA9PSAwKSAmJiAoIEJfQm94W21dW25dWzEwXT09MSkpewoJCWZvciAoaW50IGEgPSAxIDsgYSA8IDEwIDsgYSsrKQl7CgkJCWlmKEJfQm94W21dW25dW2EtMV09PTEpewoJCQoJCQkJYXNzaWduKEJfQm94LG0sbixhKTsKCQkKCQkJCgkJCX0vL2lmCgkJCX0vL2ZvciBhCgoJCX0vL2lmCgl9Ly9mb3IgagoJfS8vZm9yIC8vaQoJCQkKfQoKcHVibGljIHN0YXRpYyB2b2lkIGlzX3NvbHZlZChpbnRbXVtdW10gIEJfQm94KSB7Cgpmb3IoaW50IGkgPSAwOyBpPDkgOyBpKyspewoJZm9yKGludCBqID0gMDsgajw5IDsgaisrKXsKCQoJaWYoKEJfQm94W2ldW2pdWzldID09IDApICYmICggQl9Cb3hbaV1bal1bMTBdPT0xKSl7CgkJZm9yIChpbnQgYSA9IDAgOyBhIDwgOSA7IGErKykJewoJCWlmICggQl9Cb3hbaV1bal1bYV09PTEpCXsKCQoJCWFzc2lnbihCX0JveCxpLGosYSsxKTsKCX0vL2lmCgkJfS8vZm9yYQoJCX0vL2lmIAoJCX0vL2ZvcmoKfS8vZm9yIGkKCn0gCgoKcHVibGljIHN0YXRpYyB2b2lkIGFzc2lnbihpbnRbXVtdW10gIEJfQm94LCBpbnQgcixpbnQgYywgaW50IHZhbCkgewoKQl9Cb3hbcl1bY11bOV09IHZhbDsKQl9Cb3hbcl1bY11bMTBdPTE7CkJfQm94W3JdW2NdW3ZhbC0xXT0xOwpmb3IgKGludCBpID0gMDsgaSA8IDk7IGkrKyl7CglpZihpIT0odmFsLTEpKXsKCUJfQm94W3JdW2NdW2ldPTA7Cgl9Ly9pZgp9Ly9mb3IgaQpjaGFuZ2VfbWFya3Nfc2FtZV9iaWdfYm94KEJfQm94LHIsYyx2YWwpOwpjaGFuZ2VfbWFya3Nfc2FtZV9yb3coQl9Cb3gscixjLHZhbCk7CmNoYW5nZV9tYXJrc19zYW1lX2NvbHVtbihCX0JveCxyLGMsdmFsKTsKaXNfdW5pcXVlKEJfQm94KTsKLy9pc19zb2x2ZWQoQkJCb3gpOwoKfSAKCn0=