#include using namespace std; // piece numberLL, piece orientation/positionLL, data 1/2. unsigned long long ap[] = { 0x0000000000000207LL, 0x000000000000081cLL, 0x0000000000040604LL, 0x0000000000002070LL, 0x0000000000101810LL, 0x0000000000406040LL, 0x0000000000040e00LL, 0x0000000002030200LL, 0x0000000000103800LL, 0x00000000080c0800LL, 0x000000000040e000LL, 0x0000000020302000LL, 0x0000000080c08000LL, 0x0000000002070000LL, 0x00000000081c0000LL, 0x0000000406040000LL, 0x0000000020700000LL, 0x0000001018100000LL, 0x0000004060400000LL, 0x000000040e000000LL, 0x0000020302000000LL, 0x0000001038000000LL, 0x0000080c08000000LL, 0x00000040e0000000LL, 0x0000203020000000LL, 0x000080c080000000LL, 0x0000020700000000LL, 0x0000081c00000000LL, 0x0004060400000000LL, 0x0000207000000000LL, 0x0010181000000000LL, 0x0040604000000000LL, 0x00040e0000000000LL, 0x0010380000000000LL, 0x0040e00000000000LL, }; unsigned long long bp[] = { 0x000000000000040eLL, 0x0000000000000702LL, 0x0000000000020302LL, 0x0000000000020602LL, 0x0000000000001038LL, 0x0000000000001c08LL, 0x0000000000080c08LL, 0x0000000000081808LL, 0x00000000000040e0LL, 0x0000000000007020LL, 0x0000000000203020LL, 0x0000000000206020LL, 0x000000000080c080LL, 0x0000000000020700LL, 0x0000000001030100LL, 0x0000000000081c00LL, 0x00000000000e0400LL, 0x0000000004060400LL, 0x00000000040c0400LL, 0x0000000000207000LL, 0x0000000000381000LL, 0x0000000010181000LL, 0x0000000010301000LL, 0x0000000000e04000LL, 0x0000000040604000LL, 0x0000000040c04000LL, 0x00000000040e0000LL, 0x0000000007020000LL, 0x0000000203020000LL, 0x0000000206020000LL, 0x0000000010380000LL, 0x000000001c080000LL, 0x000000080c080000LL, 0x0000000818080000LL, 0x0000000040e00000LL, 0x0000000070200000LL, 0x0000002030200000LL, 0x0000002060200000LL, 0x00000080c0800000LL, 0x0000000207000000LL, 0x0000010301000000LL, 0x000000081c000000LL, 0x0000000e04000000LL, 0x0000040604000000LL, 0x0000040c04000000LL, 0x0000002070000000LL, 0x0000003810000000LL, 0x0000101810000000LL, 0x0000103010000000LL, 0x000000e040000000LL, 0x0000406040000000LL, 0x000040c040000000LL, 0x0000040e00000000LL, 0x0000070200000000LL, 0x0002030200000000LL, 0x0002060200000000LL, 0x0000103800000000LL, 0x00001c0800000000LL, 0x00080c0800000000LL, 0x0008180800000000LL, 0x000040e000000000LL, 0x0000702000000000LL, 0x0020302000000000LL, 0x0020602000000000LL, 0x0080c08000000000LL, 0x0002070000000000LL, 0x00081c0000000000LL, 0x000e040000000000LL, 0x0020700000000000LL, 0x0038100000000000LL, 0x00e0400000000000LL, }; unsigned long long cp[] = { 0x000000000000000fLL, 0x0000000001010101LL, 0x000000000000001eLL, 0x0000000002020202LL, 0x000000000000003cLL, 0x0000000004040404LL, 0x0000000000000078LL, 0x0000000008080808LL, 0x00000000000000f0LL, 0x0000000010101010LL, 0x0000000020202020LL, 0x0000000040404040LL, 0x0000000080808080LL, 0x0000000000000f00LL, 0x0000000101010100LL, 0x0000000000001e00LL, 0x0000000202020200LL, 0x0000000000003c00LL, 0x0000000404040400LL, 0x0000000000007800LL, 0x0000000808080800LL, 0x000000000000f000LL, 0x0000001010101000LL, 0x0000002020202000LL, 0x0000004040404000LL, 0x0000008080808000LL, 0x00000000000f0000LL, 0x0000010101010000LL, 0x00000000001e0000LL, 0x0000020202020000LL, 0x00000000003c0000LL, 0x0000040404040000LL, 0x0000000000780000LL, 0x0000080808080000LL, 0x0000000000f00000LL, 0x0000101010100000LL, 0x0000202020200000LL, 0x0000404040400000LL, 0x0000808080800000LL, 0x000000000f000000LL, 0x0001010101000000LL, 0x000000001e000000LL, 0x0002020202000000LL, 0x000000003c000000LL, 0x0004040404000000LL, 0x0000000078000000LL, 0x0008080808000000LL, 0x00000000f0000000LL, 0x0010101010000000LL, 0x0020202020000000LL, 0x0040404040000000LL, 0x0080808080000000LL, 0x0000000f00000000LL, 0x0000001e00000000LL, 0x0000003c00000000LL, 0x0000007800000000LL, 0x000000f000000000LL, 0x00000f0000000000LL, 0x00001e0000000000LL, 0x00003c0000000000LL, 0x0000780000000000LL, 0x0000f00000000000LL, 0x000f000000000000LL, 0x001e000000000000LL, 0x003c000000000000LL, 0x0078000000000000LL, 0x00f0000000000000LL, }; unsigned long long dp[] = { 0x0000000000000603LL, 0x0000000000000c06LL, 0x0000000000010302LL, 0x000000000000180cLL, 0x0000000000020604LL, 0x0000000000003018LL, 0x0000000000040c08LL, 0x0000000000006030LL, 0x0000000000081810LL, 0x000000000000c060LL, 0x0000000000103020LL, 0x0000000000206040LL, 0x000000000040c080LL, 0x0000000000060300LL, 0x00000000000c0600LL, 0x0000000001030200LL, 0x0000000000180c00LL, 0x0000000002060400LL, 0x0000000000301800LL, 0x00000000040c0800LL, 0x0000000000603000LL, 0x0000000008181000LL, 0x0000000000c06000LL, 0x0000000010302000LL, 0x0000000020604000LL, 0x0000000040c08000LL, 0x0000000006030000LL, 0x000000000c060000LL, 0x0000000103020000LL, 0x00000000180c0000LL, 0x0000000206040000LL, 0x0000000030180000LL, 0x000000040c080000LL, 0x0000000060300000LL, 0x0000000818100000LL, 0x00000000c0600000LL, 0x0000001030200000LL, 0x0000002060400000LL, 0x00000040c0800000LL, 0x0000000603000000LL, 0x0000000c06000000LL, 0x0000010302000000LL, 0x000000180c000000LL, 0x0000020604000000LL, 0x0000003018000000LL, 0x0000040c08000000LL, 0x0000006030000000LL, 0x0000081810000000LL, 0x000000c060000000LL, 0x0000103020000000LL, 0x0000206040000000LL, 0x000040c080000000LL, 0x0000060300000000LL, 0x00000c0600000000LL, 0x0001030200000000LL, 0x0000180c00000000LL, 0x0002060400000000LL, 0x0000301800000000LL, 0x00040c0800000000LL, 0x0000603000000000LL, 0x0008181000000000LL, 0x0000c06000000000LL, 0x0010302000000000LL, 0x0020604000000000LL, 0x0040c08000000000LL, 0x0006030000000000LL, 0x000c060000000000LL, 0x00180c0000000000LL, 0x0030180000000000LL, 0x0060300000000000LL, 0x00c0600000000000LL, }; unsigned long long ep[] = { 0x0000000000020301LL, 0x0000000000000306LL, 0x0000000000040602LL, 0x000000000000060cLL, 0x0000000000080c04LL, 0x0000000000000c18LL, 0x0000000000101808LL, 0x0000000000001830LL, 0x0000000000203010LL, 0x0000000000003060LL, 0x0000000000406020LL, 0x00000000000060c0LL, 0x000000000080c040LL, 0x0000000002030100LL, 0x0000000000030600LL, 0x0000000004060200LL, 0x0000000000060c00LL, 0x00000000080c0400LL, 0x00000000000c1800LL, 0x0000000010180800LL, 0x0000000000183000LL, 0x0000000020301000LL, 0x0000000000306000LL, 0x0000000040602000LL, 0x000000000060c000LL, 0x0000000080c04000LL, 0x0000000203010000LL, 0x0000000003060000LL, 0x0000000406020000LL, 0x00000000060c0000LL, 0x000000080c040000LL, 0x000000000c180000LL, 0x0000001018080000LL, 0x0000000018300000LL, 0x0000002030100000LL, 0x0000000030600000LL, 0x0000004060200000LL, 0x0000000060c00000LL, 0x00000080c0400000LL, 0x0000020301000000LL, 0x0000000306000000LL, 0x0000040602000000LL, 0x000000060c000000LL, 0x0000080c04000000LL, 0x0000000c18000000LL, 0x0000101808000000LL, 0x0000001830000000LL, 0x0000203010000000LL, 0x0000003060000000LL, 0x0000406020000000LL, 0x00000060c0000000LL, 0x000080c040000000LL, 0x0002030100000000LL, 0x0000030600000000LL, 0x0004060200000000LL, 0x0000060c00000000LL, 0x00080c0400000000LL, 0x00000c1800000000LL, 0x0010180800000000LL, 0x0000183000000000LL, 0x0020301000000000LL, 0x0000306000000000LL, 0x0040602000000000LL, 0x000060c000000000LL, 0x0080c04000000000LL, 0x0003060000000000LL, 0x00060c0000000000LL, 0x000c180000000000LL, 0x0018300000000000LL, 0x0030600000000000LL, 0x0060c00000000000LL, }; unsigned long long fp[] = { 0x0000000000000701LL, 0x000000000000080eLL, 0x0000000000020206LL, 0x0000000000030202LL, 0x0000000000001c04LL, 0x0000000000002038LL, 0x0000000000080818LL, 0x00000000000c0808LL, 0x0000000000007010LL, 0x00000000000080e0LL, 0x0000000000202060LL, 0x0000000000302020LL, 0x0000000000c08080LL, 0x0000000000040700LL, 0x0000000001010300LL, 0x00000000000e0200LL, 0x0000000000101c00LL, 0x0000000004040c00LL, 0x0000000006040400LL, 0x0000000000380800LL, 0x0000000000407000LL, 0x0000000010103000LL, 0x0000000018101000LL, 0x0000000000e02000LL, 0x000000004040c000LL, 0x0000000060404000LL, 0x0000000007010000LL, 0x00000000080e0000LL, 0x0000000202060000LL, 0x0000000302020000LL, 0x000000001c040000LL, 0x0000000020380000LL, 0x0000000808180000LL, 0x0000000c08080000LL, 0x0000000070100000LL, 0x0000000080e00000LL, 0x0000002020600000LL, 0x0000003020200000LL, 0x000000c080800000LL, 0x0000000407000000LL, 0x0000010103000000LL, 0x0000000e02000000LL, 0x000000101c000000LL, 0x000004040c000000LL, 0x0000060404000000LL, 0x0000003808000000LL, 0x0000004070000000LL, 0x0000101030000000LL, 0x0000181010000000LL, 0x000000e020000000LL, 0x00004040c0000000LL, 0x0000604040000000LL, 0x0000070100000000LL, 0x0000080e00000000LL, 0x0002020600000000LL, 0x0003020200000000LL, 0x00001c0400000000LL, 0x0000203800000000LL, 0x0008081800000000LL, 0x000c080800000000LL, 0x0000701000000000LL, 0x000080e000000000LL, 0x0020206000000000LL, 0x0030202000000000LL, 0x00c0808000000000LL, 0x0004070000000000LL, 0x000e020000000000LL, 0x00101c0000000000LL, 0x0038080000000000LL, 0x0040700000000000LL, 0x00e0200000000000LL, }; unsigned long long gp[] = { 0x0000000000000107LL, 0x0000000000030101LL, 0x0000000000040406LL, 0x000000000000041cLL, 0x00000000000c0404LL, 0x0000000000101018LL, 0x0000000000000e08LL, 0x0000000000001070LL, 0x0000000000301010LL, 0x0000000000404060LL, 0x0000000000003820LL, 0x0000000000c04040LL, 0x000000000000e080LL, 0x0000000002020300LL, 0x0000000000020e00LL, 0x0000000006020200LL, 0x0000000008080c00LL, 0x0000000000070400LL, 0x0000000000083800LL, 0x0000000018080800LL, 0x0000000020203000LL, 0x00000000001c1000LL, 0x000000000020e000LL, 0x0000000060202000LL, 0x000000008080c000LL, 0x0000000000704000LL, 0x0000000001070000LL, 0x0000000301010000LL, 0x0000000404060000LL, 0x00000000041c0000LL, 0x0000000c04040000LL, 0x0000001010180000LL, 0x000000000e080000LL, 0x0000000010700000LL, 0x0000003010100000LL, 0x0000004040600000LL, 0x0000000038200000LL, 0x000000c040400000LL, 0x00000000e0800000LL, 0x0000020203000000LL, 0x000000020e000000LL, 0x0000060202000000LL, 0x000008080c000000LL, 0x0000000704000000LL, 0x0000000838000000LL, 0x0000180808000000LL, 0x0000202030000000LL, 0x0000001c10000000LL, 0x00000020e0000000LL, 0x0000602020000000LL, 0x00008080c0000000LL, 0x0000007040000000LL, 0x0000010700000000LL, 0x0003010100000000LL, 0x0004040600000000LL, 0x0000041c00000000LL, 0x000c040400000000LL, 0x0010101800000000LL, 0x00000e0800000000LL, 0x0000107000000000LL, 0x0030101000000000LL, 0x0040406000000000LL, 0x0000382000000000LL, 0x00c0404000000000LL, 0x0000e08000000000LL, 0x00020e0000000000LL, 0x0007040000000000LL, 0x0008380000000000LL, 0x001c100000000000LL, 0x0020e00000000000LL, 0x0070400000000000LL, }; unsigned long long hp[] = { 0x0000000000020203LL, 0x000000000000020eLL, 0x0000000000060202LL, 0x000000000008080cLL, 0x0000000000000704LL, 0x0000000000000838LL, 0x0000000000180808LL, 0x0000000000202030LL, 0x0000000000001c10LL, 0x00000000000020e0LL, 0x0000000000602020LL, 0x00000000008080c0LL, 0x0000000000007040LL, 0x0000000000010700LL, 0x0000000003010100LL, 0x0000000004040600LL, 0x0000000000041c00LL, 0x000000000c040400LL, 0x0000000010101800LL, 0x00000000000e0800LL, 0x0000000000107000LL, 0x0000000030101000LL, 0x0000000040406000LL, 0x0000000000382000LL, 0x00000000c0404000LL, 0x0000000000e08000LL, 0x0000000202030000LL, 0x00000000020e0000LL, 0x0000000602020000LL, 0x00000008080c0000LL, 0x0000000007040000LL, 0x0000000008380000LL, 0x0000001808080000LL, 0x0000002020300000LL, 0x000000001c100000LL, 0x0000000020e00000LL, 0x0000006020200000LL, 0x0000008080c00000LL, 0x0000000070400000LL, 0x0000000107000000LL, 0x0000030101000000LL, 0x0000040406000000LL, 0x000000041c000000LL, 0x00000c0404000000LL, 0x0000101018000000LL, 0x0000000e08000000LL, 0x0000001070000000LL, 0x0000301010000000LL, 0x0000404060000000LL, 0x0000003820000000LL, 0x0000c04040000000LL, 0x000000e080000000LL, 0x0002020300000000LL, 0x0000020e00000000LL, 0x0006020200000000LL, 0x0008080c00000000LL, 0x0000070400000000LL, 0x0000083800000000LL, 0x0018080800000000LL, 0x0020203000000000LL, 0x00001c1000000000LL, 0x000020e000000000LL, 0x0060202000000000LL, 0x008080c000000000LL, 0x0000704000000000LL, 0x0001070000000000LL, 0x00041c0000000000LL, 0x000e080000000000LL, 0x0010700000000000LL, 0x0038200000000000LL, 0x00e0800000000000LL, }; unsigned long long ip[] = { 0x0000000000000407LL, 0x0000000000010103LL, 0x0000000000000e02LL, 0x000000000000101cLL, 0x000000000004040cLL, 0x0000000000060404LL, 0x0000000000003808LL, 0x0000000000004070LL, 0x0000000000101030LL, 0x0000000000181010LL, 0x000000000000e020LL, 0x00000000004040c0LL, 0x0000000000604040LL, 0x0000000000070100LL, 0x0000000000080e00LL, 0x0000000002020600LL, 0x0000000003020200LL, 0x00000000001c0400LL, 0x0000000000203800LL, 0x0000000008081800LL, 0x000000000c080800LL, 0x0000000000701000LL, 0x000000000080e000LL, 0x0000000020206000LL, 0x0000000030202000LL, 0x00000000c0808000LL, 0x0000000004070000LL, 0x0000000101030000LL, 0x000000000e020000LL, 0x00000000101c0000LL, 0x00000004040c0000LL, 0x0000000604040000LL, 0x0000000038080000LL, 0x0000000040700000LL, 0x0000001010300000LL, 0x0000001810100000LL, 0x00000000e0200000LL, 0x0000004040c00000LL, 0x0000006040400000LL, 0x0000000701000000LL, 0x000000080e000000LL, 0x0000020206000000LL, 0x0000030202000000LL, 0x0000001c04000000LL, 0x0000002038000000LL, 0x0000080818000000LL, 0x00000c0808000000LL, 0x0000007010000000LL, 0x00000080e0000000LL, 0x0000202060000000LL, 0x0000302020000000LL, 0x0000c08080000000LL, 0x0000040700000000LL, 0x0001010300000000LL, 0x00000e0200000000LL, 0x0000101c00000000LL, 0x0004040c00000000LL, 0x0006040400000000LL, 0x0000380800000000LL, 0x0000407000000000LL, 0x0010103000000000LL, 0x0018101000000000LL, 0x0000e02000000000LL, 0x004040c000000000LL, 0x0060404000000000LL, 0x0007010000000000LL, 0x00080e0000000000LL, 0x001c040000000000LL, 0x0020380000000000LL, 0x0070100000000000LL, 0x0080e00000000000LL, }; unsigned long long jp[] = { 0x0000000000000303LL, 0x0000000000000606LL, 0x0000000000000c0cLL, 0x0000000000001818LL, 0x0000000000003030LL, 0x0000000000006060LL, 0x000000000000c0c0LL, 0x0000000000030300LL, 0x0000000000060600LL, 0x00000000000c0c00LL, 0x0000000000181800LL, 0x0000000000303000LL, 0x0000000000606000LL, 0x0000000000c0c000LL, 0x0000000003030000LL, 0x0000000006060000LL, 0x000000000c0c0000LL, 0x0000000018180000LL, 0x0000000030300000LL, 0x0000000060600000LL, 0x00000000c0c00000LL, 0x0000000303000000LL, 0x0000000606000000LL, 0x0000000c0c000000LL, 0x0000001818000000LL, 0x0000003030000000LL, 0x0000006060000000LL, 0x000000c0c0000000LL, 0x0000030300000000LL, 0x0000060600000000LL, 0x00000c0c00000000LL, 0x0000181800000000LL, 0x0000303000000000LL, 0x0000606000000000LL, 0x0000c0c000000000LL, 0x0003030000000000LL, 0x0006060000000000LL, 0x000c0c0000000000LL, 0x0018180000000000LL, 0x0030300000000000LL, 0x0060600000000000LL, 0x00c0c00000000000LL, }; unsigned long long kp[] = { 0x0000000000000203LL, 0x0000000000000301LL, 0x0000000000000206LL, 0x000000000000080cLL, 0x0000000000000604LL, 0x0000000000000c04LL, 0x0000000000000818LL, 0x0000000000002030LL, 0x0000000000001810LL, 0x0000000000003010LL, 0x0000000000002060LL, 0x00000000000080c0LL, 0x0000000000006040LL, 0x000000000000c040LL, 0x0000000000010300LL, 0x0000000000040600LL, 0x0000000000030200LL, 0x0000000000060200LL, 0x0000000000040c00LL, 0x0000000000101800LL, 0x00000000000c0800LL, 0x0000000000180800LL, 0x0000000000103000LL, 0x0000000000406000LL, 0x0000000000302000LL, 0x0000000000602000LL, 0x000000000040c000LL, 0x0000000000c08000LL, 0x0000000002030000LL, 0x0000000003010000LL, 0x0000000002060000LL, 0x00000000080c0000LL, 0x0000000006040000LL, 0x000000000c040000LL, 0x0000000008180000LL, 0x0000000020300000LL, 0x0000000018100000LL, 0x0000000030100000LL, 0x0000000020600000LL, 0x0000000080c00000LL, 0x0000000060400000LL, 0x00000000c0400000LL, 0x0000000103000000LL, 0x0000000406000000LL, 0x0000000302000000LL, 0x0000000602000000LL, 0x000000040c000000LL, 0x0000001018000000LL, 0x0000000c08000000LL, 0x0000001808000000LL, 0x0000001030000000LL, 0x0000004060000000LL, 0x0000003020000000LL, 0x0000006020000000LL, 0x00000040c0000000LL, 0x000000c080000000LL, 0x0000020300000000LL, 0x0000030100000000LL, 0x0000020600000000LL, 0x0000080c00000000LL, 0x0000060400000000LL, 0x00000c0400000000LL, 0x0000081800000000LL, 0x0000203000000000LL, 0x0000181000000000LL, 0x0000301000000000LL, 0x0000206000000000LL, 0x000080c000000000LL, 0x0000604000000000LL, 0x0000c04000000000LL, 0x0001030000000000LL, 0x0004060000000000LL, 0x0003020000000000LL, 0x0006020000000000LL, 0x00040c0000000000LL, 0x0010180000000000LL, 0x000c080000000000LL, 0x0018080000000000LL, 0x0010300000000000LL, 0x0040600000000000LL, 0x0030200000000000LL, 0x0060200000000000LL, 0x0040c00000000000LL, 0x00c0800000000000LL, }; unsigned long long lp[] = { 0x0000000000000103LL, 0x0000000000000406LL, 0x0000000000000302LL, 0x0000000000000602LL, 0x000000000000040cLL, 0x0000000000001018LL, 0x0000000000000c08LL, 0x0000000000001808LL, 0x0000000000001030LL, 0x0000000000004060LL, 0x0000000000003020LL, 0x0000000000006020LL, 0x00000000000040c0LL, 0x000000000000c080LL, 0x0000000000020300LL, 0x0000000000030100LL, 0x0000000000020600LL, 0x0000000000080c00LL, 0x0000000000060400LL, 0x00000000000c0400LL, 0x0000000000081800LL, 0x0000000000203000LL, 0x0000000000181000LL, 0x0000000000301000LL, 0x0000000000206000LL, 0x000000000080c000LL, 0x0000000000604000LL, 0x0000000000c04000LL, 0x0000000001030000LL, 0x0000000004060000LL, 0x0000000003020000LL, 0x0000000006020000LL, 0x00000000040c0000LL, 0x0000000010180000LL, 0x000000000c080000LL, 0x0000000018080000LL, 0x0000000010300000LL, 0x0000000040600000LL, 0x0000000030200000LL, 0x0000000060200000LL, 0x0000000040c00000LL, 0x00000000c0800000LL, 0x0000000203000000LL, 0x0000000301000000LL, 0x0000000206000000LL, 0x000000080c000000LL, 0x0000000604000000LL, 0x0000000c04000000LL, 0x0000000818000000LL, 0x0000002030000000LL, 0x0000001810000000LL, 0x0000003010000000LL, 0x0000002060000000LL, 0x00000080c0000000LL, 0x0000006040000000LL, 0x000000c040000000LL, 0x0000010300000000LL, 0x0000040600000000LL, 0x0000030200000000LL, 0x0000060200000000LL, 0x0000040c00000000LL, 0x0000101800000000LL, 0x00000c0800000000LL, 0x0000180800000000LL, 0x0000103000000000LL, 0x0000406000000000LL, 0x0000302000000000LL, 0x0000602000000000LL, 0x000040c000000000LL, 0x0000c08000000000LL, 0x0002030000000000LL, 0x0003010000000000LL, 0x0002060000000000LL, 0x00080c0000000000LL, 0x0006040000000000LL, 0x000c040000000000LL, 0x0008180000000000LL, 0x0020300000000000LL, 0x0018100000000000LL, 0x0030100000000000LL, 0x0020600000000000LL, 0x0080c00000000000LL, 0x0060400000000000LL, 0x00c0400000000000LL, }; unsigned long long mp[] = { 0x0000000000000007LL, 0x0000000000010101LL, 0x000000000000001cLL, 0x0000000000040404LL, 0x0000000000000070LL, 0x0000000000101010LL, 0x0000000000404040LL, 0x0000000000000e00LL, 0x0000000002020200LL, 0x0000000000003800LL, 0x0000000008080800LL, 0x000000000000e000LL, 0x0000000020202000LL, 0x0000000080808000LL, 0x0000000000070000LL, 0x0000000101010000LL, 0x00000000001c0000LL, 0x0000000404040000LL, 0x0000000000700000LL, 0x0000001010100000LL, 0x0000004040400000LL, 0x000000000e000000LL, 0x0000020202000000LL, 0x0000000038000000LL, 0x0000080808000000LL, 0x00000000e0000000LL, 0x0000202020000000LL, 0x0000808080000000LL, 0x0000000700000000LL, 0x0001010100000000LL, 0x0000001c00000000LL, 0x0004040400000000LL, 0x0000007000000000LL, 0x0010101000000000LL, 0x0040404000000000LL, 0x00000e0000000000LL, 0x0000380000000000LL, 0x0000e00000000000LL, }; unsigned long long np[] = { 0x000000000000000eLL, 0x0000000000020202LL, 0x0000000000000038LL, 0x0000000000080808LL, 0x00000000000000e0LL, 0x0000000000202020LL, 0x0000000000808080LL, 0x0000000000000700LL, 0x0000000001010100LL, 0x0000000000001c00LL, 0x0000000004040400LL, 0x0000000000007000LL, 0x0000000010101000LL, 0x0000000040404000LL, 0x00000000000e0000LL, 0x0000000202020000LL, 0x0000000000380000LL, 0x0000000808080000LL, 0x0000000000e00000LL, 0x0000002020200000LL, 0x0000008080800000LL, 0x0000000007000000LL, 0x0000010101000000LL, 0x000000001c000000LL, 0x0000040404000000LL, 0x0000000070000000LL, 0x0000101010000000LL, 0x0000404040000000LL, 0x0000000e00000000LL, 0x0002020200000000LL, 0x0000003800000000LL, 0x0008080800000000LL, 0x000000e000000000LL, 0x0020202000000000LL, 0x0080808000000000LL, 0x0000070000000000LL, 0x00001c0000000000LL, 0x0000700000000000LL, 0x000e000000000000LL, 0x0038000000000000LL, 0x00e0000000000000LL, }; unsigned long long op[] = { 0x0000000000000003LL, 0x0000000000000101LL, 0x0000000000000006LL, 0x0000000000000202LL, 0x000000000000000cLL, 0x0000000000000404LL, 0x0000000000000018LL, 0x0000000000000808LL, 0x0000000000000030LL, 0x0000000000001010LL, 0x0000000000000060LL, 0x0000000000002020LL, 0x00000000000000c0LL, 0x0000000000004040LL, 0x0000000000008080LL, 0x0000000000000300LL, 0x0000000000010100LL, 0x0000000000000600LL, 0x0000000000020200LL, 0x0000000000000c00LL, 0x0000000000040400LL, 0x0000000000001800LL, 0x0000000000080800LL, 0x0000000000003000LL, 0x0000000000101000LL, 0x0000000000006000LL, 0x0000000000202000LL, 0x000000000000c000LL, 0x0000000000404000LL, 0x0000000000808000LL, 0x0000000000030000LL, 0x0000000001010000LL, 0x0000000000060000LL, 0x0000000002020000LL, 0x00000000000c0000LL, 0x0000000004040000LL, 0x0000000000180000LL, 0x0000000008080000LL, 0x0000000000300000LL, 0x0000000010100000LL, 0x0000000000600000LL, 0x0000000020200000LL, 0x0000000000c00000LL, 0x0000000040400000LL, 0x0000000080800000LL, 0x0000000003000000LL, 0x0000000101000000LL, 0x0000000006000000LL, 0x0000000202000000LL, 0x000000000c000000LL, 0x0000000404000000LL, 0x0000000018000000LL, 0x0000000808000000LL, 0x0000000030000000LL, 0x0000001010000000LL, 0x0000000060000000LL, 0x0000002020000000LL, 0x00000000c0000000LL, 0x0000004040000000LL, 0x0000008080000000LL, 0x0000000300000000LL, 0x0000010100000000LL, 0x0000000600000000LL, 0x0000020200000000LL, 0x0000000c00000000LL, 0x0000040400000000LL, 0x0000001800000000LL, 0x0000080800000000LL, 0x0000003000000000LL, 0x0000101000000000LL, 0x0000006000000000LL, 0x0000202000000000LL, 0x000000c000000000LL, 0x0000404000000000LL, 0x0000808000000000LL, 0x0000030000000000LL, 0x0001010000000000LL, 0x0000060000000000LL, 0x0002020000000000LL, 0x00000c0000000000LL, 0x0004040000000000LL, 0x0000180000000000LL, 0x0008080000000000LL, 0x0000300000000000LL, 0x0010100000000000LL, 0x0000600000000000LL, 0x0020200000000000LL, 0x0000c00000000000LL, 0x0040400000000000LL, 0x0080800000000000LL, 0x0003000000000000LL, 0x0006000000000000LL, 0x000c000000000000LL, 0x0018000000000000LL, 0x0030000000000000LL, 0x0060000000000000LL, 0x00c0000000000000LL, }; unsigned long long pp[] = { 0x0000000000000002LL, 0x0000000000000008LL, 0x0000000000000020LL, 0x0000000000000080LL, 0x0000000000000100LL, 0x0000000000000400LL, 0x0000000000001000LL, 0x0000000000004000LL, 0x0000000000020000LL, 0x0000000000080000LL, 0x0000000000200000LL, 0x0000000000800000LL, 0x0000000001000000LL, 0x0000000004000000LL, 0x0000000010000000LL, 0x0000000040000000LL, 0x0000000200000000LL, 0x0000000800000000LL, 0x0000002000000000LL, 0x0000008000000000LL, 0x0000010000000000LL, 0x0000040000000000LL, 0x0000100000000000LL, 0x0000400000000000LL, 0x0002000000000000LL, 0x0008000000000000LL, 0x0020000000000000LL, 0x0080000000000000LL, }; unsigned long long qp[] = { 0x0000000000000001LL, 0x0000000000000004LL, 0x0000000000000010LL, 0x0000000000000040LL, 0x0000000000000200LL, 0x0000000000000800LL, 0x0000000000002000LL, 0x0000000000008000LL, 0x0000000000010000LL, 0x0000000000040000LL, 0x0000000000100000LL, 0x0000000000400000LL, 0x0000000002000000LL, 0x0000000008000000LL, 0x0000000020000000LL, 0x0000000080000000LL, 0x0000000100000000LL, 0x0000000400000000LL, 0x0000001000000000LL, 0x0000004000000000LL, 0x0000020000000000LL, 0x0000080000000000LL, 0x0000200000000000LL, 0x0000800000000000LL, }; unsigned long long* pieces[17]; unsigned long long grid = 0xFF00000000000000LL; int pieceori[17]; int piecesize[17]; unsigned long long solcount; void print() { unsigned long long placed[17]; for (int i=0;i<17;i++) { placed[i] = pieces[i][pieceori[i]]; cout << pieceori[i] << ","; } cout << "\n"; unsigned long long gridtemp = grid; for (int i=0;i<7;i++) { for (int j=0;j<8;j++) { if (gridtemp & 1) { for (int k=0;k<17;k++) { if ((pieceori[k] != -1) && (placed[k] & 1)) { cout << (char)(k+'A'); } } } else { cout << "."; } for (int k=0;k<17;k++) { if (pieceori[k] != -1) placed[k] >>= 1; } gridtemp >>= 1; } cout << "\n"; } } void recurse(const int piecenum) { if (piecenum < 8) { cout << "progress: " << solcount << "\n"; print(); } if (piecenum >= 17) { // found solution solcount++; if (solcount % 1000000 == 0) { cout << "Solcount: " << solcount << "\n"; print(); } return; } unsigned long long hole = (grid+1) ^ (grid); for (int piece=0;piece<17;piece++) { if (pieceori[piece] != -1) continue; for (int offset=0;offset < piecesize[piece];offset++) { unsigned long long firstfit; firstfit = (pieces[piece][offset]-1) ^ pieces[piece][offset]; if (firstfit > hole) break; if (firstfit < hole) continue; if (grid & pieces[piece][offset]) continue; grid |= pieces[piece][offset]; pieceori[piece] = offset; recurse(piecenum+1); pieceori[piece] = -1; grid &= ~(pieces[piece][offset]); } } } int main() { solcount = 0; for (int i=0;i<17;i++) pieceori[i] = -1; pieces[0] = ap; pieces[1] = bp; pieces[2] = cp; pieces[3] = dp; pieces[4] = ep; pieces[5] = fp; pieces[6] = gp; pieces[7] = hp; pieces[8] = ip; pieces[9] = jp; pieces[10] = kp; pieces[11] = lp; pieces[12] = mp; pieces[13] = np; pieces[14] = op; pieces[15] = pp; pieces[16] = qp; piecesize[0] = sizeof(ap)/8; piecesize[1] = sizeof(bp)/8; piecesize[2] = sizeof(cp)/8; piecesize[3] = sizeof(dp)/8; piecesize[4] = sizeof(ep)/8; piecesize[5] = sizeof(fp)/8; piecesize[6] = sizeof(gp)/8; piecesize[7] = sizeof(hp)/8; piecesize[8] = sizeof(ip)/8; piecesize[9] = sizeof(jp)/8; piecesize[10] = sizeof(kp)/8; piecesize[11] = sizeof(lp)/8; piecesize[12] = sizeof(mp)/8; piecesize[13] = sizeof(np)/8; piecesize[14] = sizeof(op)/8; piecesize[15] = sizeof(pp)/8; piecesize[16] = sizeof(qp)/8; recurse(0); cout << "Total solutions: " << solcount << "\n"; }