dvgrn wrote: ↑September 21st, 2022, 9:59 pm
... And it works! Next up, for some future post: make the binary-search minimizing part of the script
also run a whole lot faster than the previous script.
Haven't had a whole lot of time to work on this lately. But short steps are best anyway... I think this is a successful addition of a binary search for the first glider position, with a couple of TODOs after that to explain what else needs to be done to complete the optimizer script:
Code: Select all
# new-binary-slow-salvo-optimizer.py
import golly as g
LONG_ENOUGH = 4096 # running each intermediate target plus a single glider for this long should produce the next intermediate target
MIN_DELTA = 5 # only optimize down to a safe distance (two blank lanes between adjacent slow gliders)
INITIAL_DELTA = MIN_DELTA + 256 # it should be safe (producing the desired output) to build the entire slow salvo at this offset
# the distance between min and initial might as well be a power of two, but it's not necessary
offset = 0
EOlist = [ g.parse("3o$o$bo!",-1,0), g.parse("bo$2o$obo!") ]
lanes = [9, 15, -1, 31, 19, -3, -5, 1, 5, 3, 9, 25, 31, 51, 37, 11, 43, -5, -13, -13, -7, 7, -23, -39, 15, 19, 33, 21, -3, 17, 11, 23, 63, 83, 83, 67, 95, 95, 103, -55, -61, -57, -69, -51, -83, -87, -85, -81, -87, -87, -109, -71, -75, -59, -79, -63, -69, -53, -77, -75, -53, -15, -11, -19, -25, -15, -11, -35, -39, -23, -51, -51, -59, 9, 15, 27, 9, 45, 45, 31, 45, 3, 9, 25, 35, 13, 13, 31, 31, 47, 13, 19, 15, 27, 47, 3, 5, -21, -85, -45, 7, -25, -25, 5, -19, -27, -23, -23, -33, -25, -17, 3, -27, 3, 9, 9, 7, 21, 13, 13, 11, -5, -19, -19, -1, 47, 37, 37, 41, 59, 41, 37, 63, 71, -9, -7, -3, -25, -13, -9, -15, -15, -13, -7, -3, -5, 1, 17, 23, 43, 29, 3, 35, -13, -21, -21, -15, -1, -31, -47, 7, 11, 25, 13, -11, 9, 3, 15, 55, 75, 75, 59, 87, 87, 95, -63, -69, -65, -77, -59, -91, -95, -93, -89, -95, -95, -117, -79, -83, -67, -87, -71, -77, -61, -85, -83, -61, -23, -19, -27, -33, -23, -19, -43, -47, -31, -59, -59, -67, 1, 7, 19, 1, 37, 37, 23, 37, -5, 1, 17, 27, 5, 5, 23, 23, 39, 5, 11, 7, 19, 39, -5, -3, -29, -93, -53, -1, -33, -33, -3, -27, -35, -31, -31, -41, -33, -25, -5, -35, -5, 1, 1, -1, 13, 5, 5, 3, -13, -27, -27, -9, 39, 29, 29, 33, 51, 33, 29, 55, 63, -17, -23, -7, -39, -27, -5, -21, -15, -11, -13, -7, 9, 15, 35, 21, -5, 27, -21, -29, -29, -23, -9, -39, -55, -1, 3, 17, 5, -19, 1, -5, 7, 47, 67, 67, 51, 79, 79, 87, -71, -77, -73, -85, -67, -99, -103, -101, -97, -103, -103, -125, -87, -91, -75, -95, -79, -85, -69, -93, -91, -69, -31, -27, -35, -41, -31, -27, -51, -55, -39, -67, -67, -75, -7, -1, 11, -7, 29, 29, 15, 29, -13, -7, 9, 19, -3, -3, 15, 15, 31, -3, 3, -1, 11, 31, -13, -11, -37, -101, -61, -9, -41, -41, -11, -35, -43, -39, -39, -49, -41, -33, -13, -43, -13, -7, -7, -9, 5, -3, -3, -5, -21, -35, -35, -17, 31, 21, 21, 25, 43, 25, 21, 47, 55, -7, -27, -9, -17, -13, -21, -37, -31, -31, -23, -53, -35, -29, -25, -27, -21, -5, 1, 21, 7, -19, 13, -35, -43, -43, -37, -23, -53, -69, -15, -11, 3, -9, -33, -13, -19, -7, 33, 53, 53, 37, 65, 65, 73, -85, -91, -87, -99, -81, -113, -117, -115, -111, -117, -117, -139, -101, -105, -89, -109, -93, -99, -83, -107, -105, -83, -45, -41, -49, -55, -45, -41, -65, -69, -53, -81, -81, -89, -21, -15, -3, -21, 15, 15, 1, 15, -27, -21, -5, 5, -17, -17, 1, 1, 17, -17, -11, -15, -3, 17, -27, -25, -51, -115, -75, -23, -55, -55, -25, -49, -57, -53, -53, -63, -55, -47, -27, -57, -27, -21, -21, -23, -9, -17, -17, -19, -35, -49, -49, -31, 17, 7, 7, 11, 29, 11, 7, 33, 41, -21, -3, -3, 5, -15, -15, -1, -19, -13, -9, -11, -5, 11, 17, 37, 23, -3, 29, -19, -27, -27, -21, -7, -37, -53, 1, 5, 19, 7, -17, 3, -3, 9, 49, 69, 69, 53, 81, 81, 89, -69, -75, -71, -83, -65, -97, -101, -99, -95, -101, -101, -123, -85, -89, -73, -93, -77, -83, -67, -91, -89, -67, -29, -25, -33, -39, -29, -25, -49, -53, -37, -65, -65, -73, -5, 1, 13, -5, 31, 31, 17, 31, -11, -5, 11, 21, -1, -1, 17, 17, 33, -1, 5, 1, 13, 33, -11, -9, -35, -99, -59, -7, -39, -39, -9, -33, -41, -37, -37, -47, -39, -31, -11, -41, -11, -5, -5, -7, 7, -1, -1, -3, -19, -33, -33, -15, 33, 23, 23, 27, 45, 27, 23, 49, 57, -23, -29, 1, 19, 5, -27, 13, -3, 3, 7, 5, 11, 27, 33, 53, 39, 13, 45, -3, -11, -11, -5, 9, -21, -37, 17, 21, 35, 23, -1, 19, 13, 25, 65, 85, 85, 69, 97, 97, 105, -53, -59, -55, -67, -49, -81, -85, -83, -79, -85, -85, -107, -69, -73, -57, -77, -61, -67, -51, -75, -73, -51, -13, -9, -17, -23, -13, -9, -33, -37, -21, -49, -49, -57, 11, 17, 29, 11, 47, 47, 33, 47, 5, 11, 27, 37, 15, 15, 33, 33, 49, 15, 21, 17, 29, 49, 5, 7, -19, -83, -43, 9, -23, -23, 7, -17, -25, -21, -21, -31, -23, -15, 5, -25, 5, 11, 11, 9, 23, 15, 15, 13, -3, -17, -17, 1, 49, 39, 39, 43, 61, 43, 39, 65, 73, 11, 17, 33, 11, 1, -31, -5, 1, 5, 3, 9, 25, 31, 51, 37, 11, 43, -5, -13, -13, -7, 7, -23, -39, 15, 19, 33, 21, -3, 17, 11, 23, 63, 83, 83, 67, 95, 95, 103, -55, -61, -57, -69, -51, -83, -87, -85, -81, -87, -87, -109, -71, -75, -59, -79, -63, -69, -53, -77, -75, -53, -15, -11, -19, -25, -15, -11, -35, -39, -23, -51, -51, -59, 9, 15, 27, 9, 45, 45, 31, 45, 3, 9, 25, 35, 13, 13, 31, 31, 47, 13, 19, 15, 27, 47, 3, 5, -21, -85, -45, 7, -25, -25, 5, -19, -27, -23, -23, -33, -25, -17, 3, -27, 3, 9, 9, 7, 21, 13, 13, 11, -5, -19, -19, -1, 47, 37, 37, 41, 59, 41, 37, 63, 71, -9, -3, 1, -9, -1, -7, -1, 3, 1, 7, 39, 23, 29, 49, 35, 9, 41, -7, -15, -15, -9, 5, -25, -41, 13, 17, 31, 19, -5, 15, 9, 21, 61, 81, 81, 65, 93, 93, 101, -57, -63, -59, -71, -53, -85, -89, -87, -83, -89, -89, -111, -73, -77, -61, -81, -65, -71, -55, -79, -77, -55, -17, -13, -21, -27, -17, -13, -37, -41, -25, -53, -53, -61, 7, 13, 25, 7, 43, 43, 29, 43, 1, 7, 23, 33, 11, 11, 29, 29, 45, 11, 17, 13, 25, 45, 1, 3, -23, -87, -47, 5, -27, -27, 3, -21, -29, -25, -25, -35, -27, -19, 1, -29, 1, 7, 7, 5, 19, 11, 11, 9, -7, -21, -21, -3, 45, 35, 35, 39, 57, 39, 35, 61, 69, -11, -5, -11, -19, -17, -13, -19, 7, -25, -45, -15, -9, -21, -15, -11, -13, -7, 9, 15, 35, 21, -5, 27, -21, -29, -29, -23, -9, -39, -55, -1, 3, 17, 5, -19, 1, -5, 7, 47, 67, 67, 51, 79, 79, 87, -71, -77, -73, -85, -67, -99, -103, -101, -97, -103, -103, -125, -87, -91, -75, -95, -79, -85, -69, -93, -91, -69, -31, -27, -35, -41, -31, -27, -51, -55, -39, -67, -67, -75, -7, -1, 11, -7, 29, 29, 15, 29, -13, -7, 9, 19, -3, -3, 15, 15, 31, -3, 3, -1, 11, 31, -13, -11, -37, -101, -61, -9, -41, -41, -11, -35, -43, -39, -39, -49, -41, -33, -13, -43, -13, -7, -7, -9, 5, -3, -3, -5, -21, -35, -35, -17, 31, 21, 21, 25, 43, 25, 21, 47, 55, -25, -19, -29, -45, -23, -27, -31, -25, -21, -23, -17, -1, 5, 25, 11, -15, 17, -31, -39, -39, -33, -19, -49, -65, -11, -7, 7, -5, -29, -9, -15, -3, 37, 57, 57, 41, 69, 69, 77, -81, -87, -83, -95, -77, -109, -113, -111, -107, -113, -113, -135, -97, -101, -85, -105, -89, -95, -79, -103, -101, -79, -41, -37, -45, -51, -41, -37, -61, -65, -49, -77, -77, -85, -17, -11, 1, -17, 19, 19, 5, 19, -23, -17, -1, 9, -13, -13, 5, 5, 21, -13, -7, -11, 1, 21, -23, -21, -47, -111, -71, -19, -51, -51, -21, -45, -53, -49, -49, -59, -51, -43, -23, -53, -23, -17, -17, -19, -5, -13, -13, -15, -31, -45, -45, -27, 21, 11, 11, 15, 33, 15, 11, 37, 45, -17, -13, -13, -17, -43, -21, -13, -15, -9, -5, -7, -1, 15, 21, 41, 27, 1, 33, -15, -23, -23, -17, -3, -33, -49, 5, 9, 23, 11, -13, 7, 1, 13, 53, 73, 73, 57, 85, 85, 93, -65, -71, -67, -79, -61, -93, -97, -95, -91, -97, -97, -119, -81, -85, -69, -89, -73, -79, -63, -87, -85, -63, -25, -21, -29, -35, -25, -21, -45, -49, -33, -61, -61, -69, -1, 5, 17, -1, 35, 35, 21, 35, -7, -1, 15, 25, 3, 3, 21, 21, 37, 3, 9, 5, 17, 37, -7, -5, -31, -95, -55, -3, -35, -35, -5, -29, -37, -33, -33, -43, -35, -27, -7, -37, -7, -1, -1, -3, 11, 3, 3, 1, -15, -29, -29, -11, 37, 27, 27, 31, 49, 31, 27, 53, 61, -19, -13, -23, -39, -17, -21, -25, -19, -15, -17, -11, 5, 11, 31, 17, -9, 23, -25, -33, -33, -27, -13, -43, -59, -5, -1, 13, 1, -23, -3, -9, 3, 43, 63, 63, 47, 75, 75, 83, -75, -81, -77, -89, -71, -103, -107, -105, -101, -107, -107, -129, -91, -95, -79, -99, -83, -89, -73, -97, -95, -73, -35, -31, -39, -45, -35, -31, -55, -59, -43, -71, -71, -79, -11, -5, 7, -11, 25, 25, 11, 25, -17, -11, 5, 15, -7, -7, 11, 11, 27, -7, -1, -5, 7, 27, -17, -15, -41, -105, -65, -13, -45, -45, -15, -39, -47, -43, -43, -53, -45, -37, -17, -47, -17, -11, -11, -13, 1, -7, -7, -9, -25, -39, -39, -21, 27, 17, 17, 21, 39, 21, 17, 43, 51, -11, -5, -21, 11, -1, -23, -25, -19, -15, -17, -11, 5, 11, 31, 17, -9, 23, -25, -33, -33, -27, -13, -43, -59, -5, -1, 13, 1, -23, -3, -9, 3, 43, 63, 63, 47, 75, 75, 83, -75, -81, -77, -89, -71, -103, -107, -105, -101, -107, -107, -129, -91, -95, -79, -99, -83, -89, -73, -97, -95, -73, -35, -31, -39, -45, -35, -31, -55, -59, -43, -71, -71, -79, -11, -5, 7, -11, 25, 25, 11, 25, -17, -11, 5, 15, -7, -7, 11, 11, 27, -7, -1, -5, 7, 27, -17, -15, -41, -105, -65, -13, -45, -45, -15, -39, -47, -43, -43, -53, -45, -37, -17, -47, -17, -11, -11, -13, 1, -7, -7, -9, -25, -39, -39, -21, 27, 17, 17, 21, 39, 21, 17, 43, 51, -11, -19, -35, -19, -9, -27, -9, -3, 1, -1, 5, 21, 27, 47, 33, 7, 39, -9, -17, -17, -11, 3, -27, -43, 11, 15, 29, 17, -7, 13, 7, 19, 59, 79, 79, 63, 91, 91, 99, -59, -65, -61, -73, -55, -87, -91, -89, -85, -91, -91, -113, -75, -79, -63, -83, -67, -73, -57, -81, -79, -57, -19, -15, -23, -29, -19, -15, -39, -43, -27, -55, -55, -63, 5, 11, 23, 5, 41, 41, 27, 41, -1, 5, 21, 31, 9, 9, 27, 27, 43, 9, 15, 11, 23, 43, -1, 1, -25, -89, -49, 3, -29, -29, 1, -23, -31, -27, -27, -37, -29, -21, -1, -31, -1, 5, 5, 3, 17, 9, 9, 7, -9, -23, -23, -5, 43, 33, 33, 37, 55, 37, 33, 59, 67, 5, 9, -5, 5, -3, -15, -9, -5, -7, -1, 15, 21, 41, 27, 1, 33, -15, -43, -23, -23, -17, -3, -33, -49, 5, 9, 23, 11, -13, 7, 1, 13, 53, 73, 73, 57, 85, 85, 93, -65, -71, -67, -79, -61, -93, -97, -95, -91, -97, -97, -119, -81, -85, -69, -89, -73, -79, -63, -87, -85, -63, -25, -21, -29, -35, -25, -21, -45, -49, -33, -61, -61, -69, -1, 5, 17, -1, 35, 35, 21, 35, -7, -1, 15, 25, 3, 3, 21, 21, 37, 3, 9, 5, 17, 37, -7, -5, -31, -95, -55, -3, -35, -35, -5, -29, -37, -33, -33, -43, -35, -27, -7, -37, -7, -1, -1, -3, 11, 3, 3, 1, -15, -29, -29, -11, 37, 27, 27, 31, 49, 31, 27, 53, 61, -1, 17, 3, -17, -1, -3, -1, 5, 9, 7, 13, 29, 35, 55, 41, 15, 47, -1, -9, -9, -3, 11, -19, -35, 19, 23, 37, 25, 1, 21, 15, 27, 67, 87, 87, 71, 99, 99, 107, -51, -57, -53, -65, -47, -79, -83, -81, -77, -83, -83, -105, -67, -71, -55, -75, -59, -65, -49, -73, -71, -49, -11, -7, -15, -21, -11, -7, -31, -35, -19, -47, -47, -55, 13, 19, 31, 13, 49, 49, 35, 49, 7, 13, 29, 39, 17, 17, 35, 35, 51, 17, 23, 19, 31, 51, 7, 9, -17, -81, -41, 11, -21, -21, 9, -15, -23, -19, -19, -29, -21, -13, 7, -23, 7, 13, 13, 11, 25, 17, 17, 15, -1, -15, -15, 3, 51, 41, 41, 45, 63, 45, 41, 67, 75, -5, -19, -3, 23, 33, 9, 15, 19, 17, 23, 39, 45, 65, 51, 25, 57, 9, 1, 1, 7, 21, -9, -25, 29, 33, 47, 35, 11, 31, 25, 37, 77, 97, 97, 81, 109, 109, 117, -41, -47, -43, -55, -37, -69, -73, -71, -67, -73, -73, -95, -57, -61, -45, -65, -49, -55, -39, -63, -61, -39, -1, 3, -5, -11, -1, 3, -21, -25, -9, -37, -37, -45, 23, 29, 41, 23, 59, 59, 45, 59, 17, 23, 39, 49, 27, 27, 45, 45, 61, 27, 33, 29, 41, 61, 17, 19, -7, -71, -31, 21, -11, -11, 19, -5, -13, -9, -9, -19, -11, -3, 17, -13, 17, 23, 23, 21, 35, 27, 27, 25, 9, -5, -5, 13, 61, 51, 51, 55, 73, 55, 51, 77, 85, 23, 27, 17, 11, 17, 9, 7, 13, 17, 15, 21, 37, 43, 63, 49, 23, 55, 7, -1, -1, 5, 19, -11, -27, 27, 31, 45, 33, 9, 29, 23, 35, 75, 95, 95, 79, 107, 107, 115, -43, -49, -45, -57, -39, -71, -75, -73, -69, -75, -75, -97, -59, -63, -47, -67, -51, -57, -41, -65, -63, -41, -3, 1, -7, -13, -3, 1, -23, -27, -11, -39, -39, -47, 21, 27, 39, 21, 57, 57, 43, 57, 15, 21, 37, 47, 25, 25, 43, 43, 59, 25, 31, 27, 39, 59, 15, 17, -9, -73, -33, 19, -13, -13, 17, -7, -15, -11, -11, -21, -13, -5, 15, -15, 15, 21, 21, 19, 33, 25, 25, 23, 7, -7, -7, 11, 59, 49, 49, 53, 71, 53, 49, 75, 83, 21, 13, -3, 13, 23, 5, 23, 29, 33, 31, 37, 53, 59, 79, 65, 39, 71, 23, 15, 15, 21, 35, 5, -11, 43, 47, 61, 49, 25, 45, 39, 51, 91, 111, 111, 95, 123, 123, 131, -27, -33, -29, -41, -23, -55, -59, -57, -53, -59, -59, -81, -43, -47, -31, -51, -35, -41, -25, -49, -47, -25, 13, 17, 9, 3, 13, 17, -7, -11, 5, -23, -23, -31, 37, 43, 55, 37, 73, 73, 59, 73, 31, 37, 53, 63, 41, 41, 59, 59, 75, 41, 47, 43, 55, 75, 31, 33, 7, -57, -17, 35, 3, 3, 33, 9, 1, 5, 5, -5, 3, 11, 31, 1, 31, 37, 37, 35, 49, 41, 41, 39, 23, 9, 9, 27, 75, 65, 65, 69, 87, 69, 65, 91, 99, 19, 25, 29, 19, 27, 21, 27, 31, 29, 35, 67, 51, 57, 77, 63, 37, 69, 21, 13, 13, 19, 33, 3, -13, 41, 45, 59, 47, 23, 43, 37, 49, 89, 109, 109, 93, 121, 121, 129, -29, -35, -31, -43, -25, -57, -61, -59, -55, -61, -61, -83, -45, -49, -33, -53, -37, -43, -27, -51, -49, -27, 11, 15, 7, 1, 11, 15, -9, -13, 3, -25, -25, -33, 35, 41, 53, 35, 71, 71, 57, 71, 29, 35, 51, 61, 39, 39, 57, 57, 73, 39, 45, 41, 53, 73, 29, 31, 5, -59, -19, 33, 1, 1, 31, 7, -1, 3, 3, -7, 1, 9, 29, -1, 29, 35, 35, 33, 47, 39, 39, 37, 21, 7, 7, 25, 73, 63, 63, 67, 85, 67, 63, 89, 97, 17, 23, 13, -3, 19, 21, 7, 13, 17, 15, 21, 37, 43, 63, 49, 23, 55, 7, -1, -1, 5, 19, -11, -27, 27, 31, 45, 33, 9, 29, 23, 35, 75, 95, 95, 79, 107, 107, 115, -43, -49, -45, -57, -39, -71, -75, -73, -69, -75, -75, -97, -59, -63, -47, -67, -51, -57, -41, -65, -63, -41, -3, 1, -7, -13, -3, 1, -23, -27, -11, -39, -39, -47, 21, 27, 39, 21, 57, 57, 43, 57, 15, 21, 37, 47, 25, 25, 43, 43, 59, 25, 31, 27, 39, 59, 15, 17, -9, -73, -33, 19, -13, -13, 17, -7, -15, -11, -11, -21, -13, -5, 15, -15, 15, 21, 21, 19, 33, 25, 25, 23, 7, -7, -7, 11, 59, 49, 49, 53, 71, 53, 49, 75, 83, 21, 25, 15, -1, 21, 17, 13, 19, 23, 21, 27, 43, 49, 69, 55, 29, 61, 13, 5, 5, 11, 25, -5, -21, 33, 37, 51, 39, 15, 35, 29, 41, 81, 101, 101, 85, 113, 113, 121, -37, -43, -39, -51, -33, -65, -69, -67, -63, -69, -69, -91, -53, -57, -41, -61, -45, -51, -35, -59, -57, -35, 3, 7, -1, -7, 3, 7, -17, -21, -5, -33, -33, -41, 27, 33, 45, 27, 63, 63, 49, 63, 21, 27, 43, 53, 31, 31, 49, 49, 65, 31, 37, 33, 45, 65, 21, 23, -3, -67, -27, 25, -7, -7, 23, -1, -9, -5, -5, -15, -7, 1, 21, -9, 21, 27, 27, 25, 39, 31, 31, 29, 13, -1, -1, 17, 65, 55, 55, 59, 77, 59, 55, 81, 89, 27, 31, 21, 5, 27, 29, 15, 21, 25, 23, 29, 45, 51, 71, 57, 31, 63, 15, 7, 7, 13, 27, -3, -19, 35, 39, 53, 41, 17, 37, 31, 43, 83, 103, 103, 87, 115, 115, 123, -35, -41, -37, -49, -31, -63, -67, -65, -61, -67, -67, -89, -51, -55, -39, -59, -43, -49, -33, -57, -55, -33, 5, 9, 1, -5, 5, 9, -15, -19, -3, -31, -31, -39, 29, 35, 47, 29, 65, 65, 51, 65, 23, 29, 45, 55, 33, 33, 51, 51, 67, 33, 39, 35, 47, 67, 23, 25, -1, -65, -25, 27, -5, -5, 25, 1, -7, -3, -3, -13, -5, 3, 23, -7, 23, 29, 29, 27, 41, 33, 33, 31, 15, 1, 1, 19, 67, 57, 57, 61, 79, 61, 57, 83, 91, 29, 47, 33, 13, 29, 35, 21, 27, 31, 29, 35, 51, 57, 77, 63, 37, 69, 21, 13, 13, 19, 33, 3, -13, 41, 45, 59, 47, 23, 43, 37, 49, 89, 109, 109, 93, 121, 121, 129, -29, -35, -31, -43, -25, -57, -61, -59, -55, -61, -61, -83, -45, -49, -33, -53, -37, -43, -27, -51, -49, -27, 11, 15, 7, 1, 11, 15, -9, -13, 3, -25, -25, -33, 35, 41, 53, 35, 71, 71, 57, 71, 29, 35, 51, 61, 39, 39, 57, 57, 73, 39, 45, 41, 53, 73, 29, 31, 5, -59, -19, 33, 1, 1, 31, 7, -1, 3, 3, -7, 1, 9, 29, -1, 29, 35, 35, 33, 47, 39, 39, 37, 21, 7, 7, 25, 73, 63, 63, 67, 85, 67, 63, 89, 97, 17, 3, 27, 21, 25, 45, 31, 37, 41, 39, 45, 61, 67, 87, 73, 47, 79, 31, 23, 23, 29, 43, 13, -3, 51, 55, 69, 57, 33, 53, 47, 59, 99, 119, 119, 103, 131, 131, 139, -19, -25, -21, -33, -15, -47, -51, -49, -45, -51, -51, -73, -35, -39, -23, -43, -27, -33, -17, -41, -39, -17, 21, 25, 17, 11, 21, 25, 1, -3, 13, -15, -15, -23, 45, 51, 63, 45, 81, 81, 67, 81, 39, 45, 61, 71, 49, 49, 67, 67, 83, 49, 55, 51, 63, 83, 39, 41, 15, -49, -9, 43, 11, 11, 41, 17, 9, 13, 13, 3, 11, 19, 39, 9, 39, 45, 45, 43, 57, 49, 49, 47, 31, 17, 17, 35, 83, 73, 73, 77, 95, 77, 73, 99, 107, 27, 27, 25, 19, 17, 15, 37, 43, 47, 45, 51, 67, 73, 93, 79, 53, 85, 37, 29, 29, 35, 49, 19, 3, 57, 61, 75, 63, 39, 59, 53, 65, 105, 125, 125, 109, 137, 137, 145, -13, -19, -15, -27, -9, -41, -45, -43, -39, -45, -45, -67, -29, -33, -17, -37, -21, -27, -11, -35, -33, -11, 27, 31, 23, 17, 27, 31, 7, 3, 19, -9, -9, -17, 51, 57, 69, 51, 87, 87, 73, 87, 45, 51, 67, 77, 55, 55, 73, 73, 89, 55, 61, 57, 69, 89, 45, 47, 21, -43, -3, 49, 17, 17, 47, 23, 15, 19, 19, 9, 17, 25, 45, 15, 45, 51, 51, 49, 63, 55, 55, 53, 37, 23, 23, 41, 89, 79, 79, 83, 101, 83, 79, 105, 113, 33, 15, 29, 49, 33, 27, 23, 29, 33, 31, 37, 53, 59, 79, 65, 39, 71, 23, 15, 15, 21, 35, 5, -11, 43, 47, 61, 49, 25, 45, 39, 51, 91, 111, 111, 95, 123, 123, 131, -27, -33, -29, -41, -23, -55, -59, -57, -53, -59, -59, -81, -43, -47, -31, -51, -35, -41, -25, -49, -47, -25, 13, 17, 9, 3, 13, 17, -7, -11, 5, -23, -23, -31, 37, 43, 55, 37, 73, 73, 59, 73, 31, 37, 53, 63, 41, 41, 59, 59, 75, 41, 47, 43, 55, 75, 31, 33, 7, -57, -17, 35, 3, 3, 33, 9, 1, 5, 5, -5, 3, 11, 31, 1, 31, 37, 37, 35, 49, 41, 41, 39, 23, 9, 9, 27, 75, 65, 65, 69, 87, 69, 65, 91, 99, 19, 13, -7, 9, -1, 43, 27, 33, 37, 35, 41, 57, 63, 83, 69, 43, 75, 27, 19, 19, 25, 39, 9, -7, 47, 51, 65, 53, 29, 49, 43, 55, 95, 115, 115, 99, 127, 127, 135, -23, -29, -25, -37, -19, -51, -55, -53, -49, -55, -55, -77, -39, -43, -27, -47, -31, -37, -21, -45, -43, -21, 17, 21, 13, 7, 17, 21, -3, -7, 9, -19, -19, -27, 41, 47, 59, 41, 77, 77, 63, 77, 35, 41, 57, 67, 45, 45, 63, 63, 79, 45, 51, 47, 59, 79, 35, 37, 11, -53, -13, 39, 7, 7, 37, 13, 5, 9, 9, -1, 7, 15, 35, 5, 35, 41, 41, 39, 53, 45, 45, 43, 27, 13, 13, 31, 79, 69, 69, 73, 91, 73, 69, 95, 103, 41, 21, 21, 13, 19, 19, 15, 21, 25, 23, 29, 45, 51, 71, 57, 31, 63, 15, 7, 7, 13, 27, -3, -19, 35, 39, 53, 41, 17, 37, 31, 43, 83, 103, 103, 87, 115, 115, 123, -35, -41, -37, -49, -31, -63, -67, -65, -61, -67, -67, -89, -51, -55, -39, -59, -43, -49, -33, -57, -55, -33, 5, 9, 1, -5, 5, 9, -15, -19, -3, -31, -31, -39, 29, 35, 47, 29, 65, 65, 51, 65, 23, 29, 45, 55, 33, 33, 51, 51, 67, 33, 39, 35, 47, 67, 23, 25, -1, -65, -25, 27, -5, -5, 25, 1, -7, -3, -3, -13, -5, 3, 23, -7, 23, 29, 29, 27, 41, 33, 33, 31, 15, 1, 1, 19, 67, 57, 57, 61, 79, 61, 57, 83, 91, 29, 33, 23, 39, 55, 29, 43, 1, 7, 11, 9, 15, 31, 37, 57, 43, 17, 49, 1, -7, -7, -1, 13, -17, -33, 21, 25, 39, 27, 3, 23, 17, 29, 69, 89, 89, 73, 101, 101, 109, -49, -55, -51, -63, -45, -77, -81, -79, -75, -81, -81, -103, -65, -69, -53, -73, -57, -63, -47, -71, -69, -47, -9, -5, -13, -19, -9, -5, -29, -33, -17, -45, -45, -53, 15, 21, 33, 15, 51, 51, 37, 51, 9, 15, 31, 41, 19, 19, 37, 37, 53, 19, 25, 21, 33, 53, 9, 11, -15, -79, -39, 13, -19, -19, 11, -13, -21, -17, -17, -27, -19, -11, 9, -21, 9, 15, 15, 13, 27, 19, 19, 17, 1, -13, -13, 5, 53, 43, 43, 47, 65, 47, 43, 69, 77, -3, -17, 7, 1, 5, 25, 11, 17, 21, 19, 25, 41, 47, 67, 53, 27, 59, 11, 3, 3, 9, 23, -7, -23, 31, 35, 49, 37, 13, 33, 27, 39, 79, 99, 99, 83, 111, 111, 119, -39, -45, -41, -53, -35, -67, -71, -69, -65, -71, -71, -93, -55, -59, -43, -63, -47, -53, -37, -61, -59, -37, 1, 5, -3, -9, 1, 5, -19, -23, -7, -35, -35, -43, 25, 31, 43, 25, 61, 61, 47, 61, 19, 25, 41, 51, 29, 29, 47, 47, 63, 29, 35, 31, 43, 63, 19, 21, -5, -69, -29, 23, -9, -9, 21, -3, -11, -7, -7, -17, -9, -1, 19, -11, 19, 25, 25, 23, 37, 29, 29, 27, 11, -3, -3, 15, 63, 53, 53, 57, 75, 57, 53, 79, 87, 25, 29, 15, 25, 17, 5, 11, 15, 13, 19, 35, 41, 61, 47, 21, 53, 5, -23, -3, -3, 3, 17, -13, -29, 25, 29, 43, 31, 7, 27, 21, 33, 73, 93, 93, 77, 105, 105, 113, -45, -51, -47, -59, -41, -73, -77, -75, -71, -77, -77, -99, -61, -65, -49, -69, -53, -59, -43, -67, -65, -43, -5, -1, -9, -15, -5, -1, -25, -29, -13, -41, -41, -49, 19, 25, 37, 19, 55, 55, 41, 55, 13, 19, 35, 45, 23, 23, 41, 41, 57, 23, 29, 25, 37, 57, 13, 15, -11, -75, -35, 17, -15, -15, 15, -9, -17, -13, -13, -23, -15, -7, 13, -17, 13, 19, 19, 17, 31, 23, 23, 21, 5, -9, -9, 9, 57, 47, 47, 51, 69, 51, 47, 73, 81, 19, 23, 13, -3, 19, 15, 11, 17, 21, 19, 25, 41, 47, 67, 53, 27, 59, 11, 3, 3, 9, 23, -7, -23, 31, 35, 49, 37, 13, 33, 27, 39, 79, 99, 99, 83, 111, 111, 119, -39, -45, -41, -53, -35, -67, -71, -69, -65, -71, -71, -93, -55, -59, -43, -63, -47, -53, -37, -61, -59, -37, 1, 5, -3, -9, 1, 5, -19, -23, -7, -35, -35, -43, 25, 31, 43, 25, 61, 61, 47, 61, 19, 25, 41, 51, 29, 29, 47, 47, 63, 29, 35, 31, 43, 63, 19, 21, -5, -69, -29, 23, -9, -9, 21, -3, -11, -7, -7, -17, -9, -1, 19, -11, 19, 25, 25, 23, 37, 29, 29, 27, 11, -3, -3, 15, 63, 53, 53, 57, 75, 57, 53, 79, 87, 7, 13, 17, 7, 15, 9, 15, 19, 17, 23, 55, 39, 45, 65, 51, 25, 57, 9, 1, 1, 7, 21, -9, -25, 29, 33, 47, 35, 11, 31, 25, 37, 77, 97, 97, 81, 109, 109, 117, -41, -47, -43, -55, -37, -69, -73, -71, -67, -73, -73, -95, -57, -61, -45, -65, -49, -55, -39, -63, -61, -39, -1, 3, -5, -11, -1, 3, -21, -25, -9, -37, -37, -45, 23, 29, 41, 23, 59, 59, 45, 59, 17, 23, 39, 49, 27, 27, 45, 45, 61, 27, 33, 29, 41, 61, 17, 19, -7, -71, -31, 21, -11, -11, 19, -5, -13, -9, -9, -19, -11, -3, 17, -13, 17, 23, 23, 21, 35, 27, 27, 25, 9, -5, -5, 13, 61, 51, 51, 55, 73, 55, 51, 77, 85, 5, -1, -21, -5, -15, 29, 13, 19, 23, 21, 27, 43, 49, 69, 55, 29, 61, 13, 5, 5, 11, 25, -5, -21, 33, 37, 51, 39, 15, 35, 29, 41, 81, 101, 101, 85, 113, 113, 121, -37, -43, -39, -51, -33, -65, -69, -67, -63, -69, -69, -91, -53, -57, -41, -61, -45, -51, -35, -59, -57, -35, 3, 7, -1, -7, 3, 7, -17, -21, -5, -33, -33, -41, 27, 33, 45, 27, 63, 63, 49, 63, 21, 27, 43, 53, 31, 31, 49, 49, 65, 31, 37, 33, 45, 65, 21, 23, -3, -67, -27, 25, -7, -7, 23, -1, -9, -5, -5, -15, -7, 1, 21, -9, 21, 27, 27, 25, 39, 31, 31, 29, 13, -1, -1, 17, 65, 55, 55, 59, 77, 59, 55, 81, 89, 9, -5, 19, 13, 17, 37, 23, 29, 33, 31, 37, 53, 59, 79, 65, 39, 71, 23, 15, 15, 21, 35, 5, -11, 43, 47, 61, 49, 25, 45, 39, 51, 91, 111, 111, 95, 123, 123, 131, -27, -33, -29, -41, -23, -55, -59, -57, -53, -59, -59, -81, -43, -47, -31, -51, -35, -41, -25, -49, -47, -25, 13, 17, 9, 3, 13, 17, -7, -11, 5, -23, -23, -31, 37, 43, 55, 37, 73, 73, 59, 73, 31, 37, 53, 63, 41, 41, 59, 59, 75, 41, 47, 43, 55, 75, 31, 33, 7, -57, -17, 35, 3, 3, 33, 9, 1, 5, 5, -5, 3, 11, 31, 1, 31, 37, 37, 35, 49, 41, 41, 39, 23, 9, 9, 27, 75, 65, 65, 69, 87, 69, 65, 91, 99, 37, 41, 31, 15, 37, 39, 25, 31, 35, 33, 39, 55, 61, 81, 67, 41, 73, 25, 17, 17, 23, 37, 7, -9, 45, 49, 63, 51, 27, 47, 41, 53, 93, 113, 113, 97, 125, 125, 133, -25, -31, -27, -39, -21, -53, -57, -55, -51, -57, -57, -79, -41, -45, -29, -49, -33, -39, -23, -47, -45, -23, 15, 19, 11, 5, 15, 19, -5, -9, 7, -21, -21, -29, 39, 45, 57, 39, 75, 75, 61, 75, 33, 39, 55, 65, 43, 43, 61, 61, 77, 43, 49, 45, 57, 77, 33, 35, 9, -55, -15, 37, 5, 5, 35, 11, 3, 7, 7, -3, 5, 13, 33, 3, 33, 39, 39, 37, 51, 43, 43, 41, 25, 11, 11, 29, 77, 67, 67, 71, 89, 71, 67, 93, 101, 39, 43, 29, 39, 31, 19, 25, 29, 27, 33, 49, 55, 75, 61, 35, 67, 19, -9, 11, 11, 17, 31, 1, -15, 39, 43, 57, 45, 21, 41, 35, 47, 87, 107, 107, 91, 119, 119, 127, -31, -37, -33, -45, -27, -59, -63, -61, -57, -63, -63, -85, -47, -51, -35, -55, -39, -45, -29, -53, -51, -29, 9, 13, 5, -1, 9, 13, -11, -15, 1, -27, -27, -35, 33, 39, 51, 33, 69, 69, 55, 69, 27, 33, 49, 59, 37, 37, 55, 55, 71, 37, 43, 39, 51, 71, 27, 29, 3, -61, -21, 31, -1, -1, 29, 5, -3, 1, 1, -9, -1, 7, 27, -3, 27, 33, 33, 31, 45, 37, 37, 35, 19, 5, 5, 23, 71, 61, 61, 65, 83, 65, 61, 87, 95, 33, 37, 27, 11, 33, 35, 21, 27, 31, 29, 35, 51, 57, 77, 63, 37, 69, 21, 13, 13, 19, 33, 3, -13, 41, 45, 59, 47, 23, 43, 37, 49, 89, 109, 109, 93, 121, 121, 129, -29, -35, -31, -43, -25, -57, -61, -59, -55, -61, -61, -83, -45, -49, -33, -53, -37, -43, -27, -51, -49, -27, 11, 15, 7, 1, 11, 15, -9, -13, 3, -25, -25, -33, 35, 41, 53, 35, 71, 71, 57, 71, 29, 35, 51, 61, 39, 39, 57, 57, 73, 39, 45, 41, 53, 73, 29, 31, 5, -59, -19, 33, 1, 1, 31, 7, -1, 3, 3, -7, 1, 9, 29, -1, 29, 35, 35, 33, 47, 39, 39, 37, 21, 7, 7, 25, 73, 63, 63, 67, 85, 67, 63, 89, 97, 17, 23, 27, 17, 25, 19, 25, 29, 27, 33, 65, 49, 55, 75, 61, 35, 67, 19, 11, 11, 17, 31, 1, -15, 39, 43, 57, 45, 21, 41, 35, 47, 87, 107, 107, 91, 119, 119, 127, -31, -37, -33, -45, -27, -59, -63, -61, -57, -63, -63, -85, -47, -51, -35, -55, -39, -45, -29, -53, -51, -29, 9, 13, 5, -1, 9, 13, -11, -15, 1, -27, -27, -35, 33, 39, 51, 33, 69, 69, 55, 69, 27, 33, 49, 59, 37, 37, 55, 55, 71, 37, 43, 39, 51, 71, 27, 29, 3, -61, -21, 31, -1, -1, 29, 5, -3, 1, 1, -9, -1, 7, 27, -3, 27, 33, 33, 31, 45, 37, 37, 35, 19, 5, 5, 23, 71, 61, 61, 65, 83, 65, 61, 87, 95, 33, 17, 31, 1, 43, 61, 49, 33, 39, 43, 41, 47, 63, 69, 89, 75, 49, 81, 33, 25, 25, 31, 45, 15, -1, 53, 57, 71, 59, 35, 55, 49, 61, 101, 121, 121, 105, 133, 133, 141, -17, -23, -19, -31, -13, -45, -49, -47, -43, -49, -49, -71, -33, -37, -21, -41, -25, -31, -15, -39, -37, -15, 23, 27, 19, 13, 23, 27, 3, -1, 15, -13, -13, -21, 47, 53, 65, 47, 83, 83, 69, 83, 41, 47, 63, 73, 51, 51, 69, 69, 85, 51, 57, 53, 65, 85, 41, 43, 17, -47, -7, 45, 13, 13, 43, 19, 11, 15, 15, 5, 13, 21, 41, 11, 41, 47, 47, 45, 59, 51, 51, 49, 33, 19, 19, 37, 85, 75, 75, 79, 97, 79, 75, 101, 109, 47, 27, 27, 19, 25, 25, 21, 27, 31, 29, 35, 51, 57, 77, 63, 37, 69, 21, 13, 13, 19, 33, 3, -13, 41, 45, 59, 47, 23, 43, 37, 49, 89, 109, 109, 93, 121, 121, 129, -29, -35, -31, -43, -25, -57, -61, -59, -55, -61, -61, -83, -45, -49, -33, -53, -37, -43, -27, -51, -49, -27, 11, 15, 7, 1, 11, 15, -9, -13, 3, -25, -25, -33, 35, 41, 53, 35, 71, 71, 57, 71, 29, 35, 51, 61, 39, 39, 57, 57, 73, 39, 45, 41, 53, 73, 29, 31, 5, -59, -19, 33, 1, 1, 31, 7, -1, 3, 3, -7, 1, 9, 29, -1, 29, 35, 35, 33, 47, 39, 39, 37, 21, 7, 7, 25, 73, 63, 63, 67, 85, 67, 63, 89, 97, 17, 23, 27, 17, 25, 19, 25, 29, 27, 33, 65, 49, 55, 75, 61, 35, 67, 19, 11, 11, 17, 31, 1, -15, 39, 43, 57, 45, 21, 41, 35, 47, 87, 107, 107, 91, 119, 119, 127, -31, -37, -33, -45, -27, -59, -63, -61, -57, -63, -63, -85, -47, -51, -35, -55, -39, -45, -29, -53, -51, -29, 9, 13, 5, -1, 9, 13, -11, -15, 1, -27, -27, -35, 33, 39, 51, 33, 69, 69, 55, 69, 27, 33, 49, 59, 37, 37, 55, 55, 71, 37, 43, 39, 51, 71, 27, 29, 3, -61, -21, 31, -1, -1, 29, 5, -3, 1, 1, -9, -1, 7, 27, -3, 27, 33, 33, 31, 45, 37, 37, 35, 19, 5, 5, 23, 71, 61, 61, 65, 83, 65, 61, 87, 95, 15, 9, -11, 5, -5, 39, 23, 29, 33, 31, 37, 53, 59, 79, 65, 39, 71, 23, 15, 15, 21, 35, 5, -11, 43, 47, 61, 49, 25, 45, 39, 51, 91, 111, 111, 95, 123, 123, 131, -27, -33, -29, -41, -23, -55, -59, -57, -53, -59, -59, -81, -43, -47, -31, -51, -35, -41, -25, -49, -47, -25, 13, 17, 9, 3, 13, 17, -7, -11, 5, -23, -23, -31, 37, 43, 55, 37, 73, 73, 59, 73, 31, 37, 53, 63, 41, 41, 59, 59, 75, 41, 47, 43, 55, 75, 31, 33, 7, -57, -17, 35, 3, 3, 33, 9, 1, 5, 5, -5, 3, 11, 31, 1, 31, 37, 37, 35, 49, 41, 41, 39, 23, 9, 9, 27, 75, 65, 65, 69, 87, 69, 65, 91, 99, 37, 41, 27, 37, 29, 17, 23, 27, 25, 31, 47, 53, 73, 59, 33, 65, 17, -11, 9, 9, 15, 29, -1, -17, 37, 41, 55, 43, 19, 39, 33, 45, 85, 105, 105, 89, 117, 117, 125, -33, -39, -35, -47, -29, -61, -65, -63, -59, -65, -65, -87, -49, -53, -37, -57, -41, -47, -31, -55, -53, -31, 7, 11, 3, -3, 7, 11, -13, -17, -1, -29, -29, -37, 31, 37, 49, 31, 67, 67, 53, 67, 25, 31, 47, 57, 35, 35, 53, 53, 69, 35, 41, 37, 49, 69, 25, 27, 1, -63, -23, 29, -3, -3, 27, 3, -5, -1, -1, -11, -3, 5, 25, -5, 25, 31, 31, 29, 43, 35, 35, 33, 17, 3, 3, 21, 69, 59, 59, 63, 81, 63, 59, 85, 93, 31, 35, 25, 15, 29, 3, 29, 35, 39, 37, 43, 59, 65, 85, 71, 45, 77, 29, 21, 21, 27, 41, 11, -5, 49, 53, 67, 55, 31, 51, 45, 57, 97, 117, 117, 101, 129, 129, 137, -21, -27, -23, -35, -17, -49, -53, -51, -47, -53, -53, -75, -37, -41, -25, -45, -29, -35, -19, -43, -41, -19, 19, 23, 15, 9, 19, 23, -1, -5, 11, -17, -17, -25, 43, 49, 61, 43, 79, 79, 65, 79, 37, 43, 59, 69, 47, 47, 65, 65, 81, 47, 53, 49, 61, 81, 37, 39, 13, -51, -11, 41, 9, 9, 39, 15, 7, 11, 11, 1, 9, 17, 37, 7, 37, 43, 43, 41, 55, 47, 47, 45, 29, 15, 15, 33, 81, 71, 71, 75, 93, 75, 71, 97, 105, 43, 47, 37, 21, 43, 39, 35, 41, 45, 43, 49, 65, 71, 91, 77, 51, 83, 35, 27, 27, 33, 47, 17, 1, 55, 59, 73, 61, 37, 57, 51, 63, 103, 123, 123, 107, 135, 135, 143, -15, -21, -17, -29, -11, -43, -47, -45, -41, -47, -47, -69, -31, -35, -19, -39, -23, -29, -13, -37, -35, -13, 25, 29, 21, 15, 25, 29, 5, 1, 17, -11, -11, -19, 49, 55, 67, 49, 85, 85, 71, 85, 43, 49, 65, 75, 53, 53, 71, 71, 87, 53, 59, 55, 67, 87, 43, 45, 19, -45, -5, 47, 15, 15, 45, 21, 13, 17, 17, 7, 15, 23, 43, 13, 43, 49, 49, 47, 61, 53, 53, 51, 35, 21, 21, 39, 87, 77, 77, 81, 99, 81, 77, 103, 111, 31, 17, 41, 35, 39, 53, 49, 55, 59, 57, 63, 79, 85, 105, 91, 65, 97, 49, 41, 41, 47, 61, 31, 15, 69, 73, 87, 75, 51, 71, 65, 77, 117, 137, 137, 121, 149, 149, 157, -1, -7, -3, -15, 3, -29, -33, -31, -27, -33, -33, -55, -17, -21, -5, -25, -9, -15, 1, -23, -21, 1, 39, 43, 35, 29, 39, 43, 19, 15, 31, 3, 3, -5, 63, 69, 81, 63, 99, 99, 85, 99, 57, 63, 79, 89, 67, 67, 85, 85, 101, 67, 73, 69, 81, 101, 57, 59, 33, -31, 9, 61, 29, 29, 59, 35, 27, 31, 31, 21, 29, 37, 57, 27, 57, 63, 63, 61, 75, 67, 67, 65, 49, 35, 35, 53, 101, 91, 91, 95, 113, 95, 91, 117, 125, 63, 67, 57, 41, 63, 65, 51, 57, 61, 59, 65, 81, 87, 107, 93, 67, 99, 51, 43, 43, 49, 63, 33, 17, 71, 75, 89, 77, 53, 73, 67, 79, 119, 139, 139, 123, 151, 151, 159, 1, -5, -1, -13, 5, -27, -31, -29, -25, -31, -31, -53, -15, -19, -3, -23, -7, -13, 3, -21, -19, 3, 41, 45, 37, 31, 41, 45, 21, 17, 33, 5, 5, -3, 65, 71, 83, 65, 101, 101, 87, 101, 59, 65, 81, 91, 69, 69, 87, 87, 103, 69, 75, 71, 83, 103, 59, 61, 35, -29, 11, 63, 31, 31, 61, 37, 29, 33, 33, 23, 31, 39, 59, 29, 59, 65, 65, 63, 77, 69, 69, 67, 51, 37, 37, 55, 103, 93, 93, 97, 115, 97, 93, 119, 127, 65, 69, 63, 73, 65, 55, 47, 45, 51, 55, 53, 59, 75, 81, 101, 87, 61, 93, 45, 37, 37, 43, 57, 27, 11, 65, 69, 83, 71, 47, 67, 61, 73, 113, 133, 133, 117, 145, 145, 153, -5, -11, -7, -19, -1, -33, -37, -35, -31, -37, -37, -59, -21, -25, -9, -29, -13, -19, -3, -27, -25, -3, 35, 39, 31, 25, 35, 39, 15, 11, 27, -1, -1, -9, 59, 65, 77, 59, 95, 95, 81, 95, 53, 59, 75, 85, 63, 63, 81, 81, 97, 63, 69, 65, 77, 97, 53, 55, 29, -35, 5, 57, 25, 25, 55, 31, 23, 27, 27, 17, 25, 33, 53, 23, 53, 59, 59, 57, 71, 63, 63, 61, 45, 31, 31, 49, 97, 87, 87, 91, 109, 91, 87, 113, 121, 41, 47, 41, 51, 49, 59, 67, 51, 57, 61, 59, 65, 81, 87, 107, 93, 67, 99, 51, 43, 43, 49, 63, 33, 17, 71, 75, 89, 77, 53, 73, 67, 79, 119, 139, 139, 123, 151, 151, 159, 1, -5, -1, -13, 5, -27, -31, -29, -25, -31, -31, -53, -15, -19, -3, -23, -7, -13, 3, -21, -19, 3, 41, 45, 37, 31, 41, 45, 21, 17, 33, 5, 5, -3, 65, 71, 83, 65, 101, 101, 87, 101, 59, 65, 81, 91, 69, 69, 87, 87, 103, 69, 75, 71, 83, 103, 59, 61, 35, -29, 11, 63, 31, 31, 61, 37, 29, 33, 33, 23, 31, 39, 59, 29, 59, 65, 65, 63, 77, 69, 69, 67, 51, 37, 37, 55, 103, 93, 93, 97, 115, 97, 93, 119, 127, 47, 53, 43, 49, 57, 47, 63, 69, 73, 71, 77, 93, 99, 119, 105, 79, 111, 63, 55, 55, 61, 75, 45, 29, 83, 87, 101, 89, 65, 85, 79, 91, 131, 151, 151, 135, 163, 163, 171, 13, 7, 11, -1, 17, -15, -19, -17, -13, -19, -19, -41, -3, -7, 9, -11, 5, -1, 15, -9, -7, 15, 53, 57, 49, 43, 53, 57, 33, 29, 45, 17, 17, 9, 77, 83, 95, 77, 113, 113, 99, 113, 71, 77, 93, 103, 81, 81, 99, 99, 115, 81, 87, 83, 95, 115, 71, 73, 47, -17, 23, 75, 43, 43, 73, 49, 41, 45, 45, 35, 43, 51, 71, 41, 71, 77, 77, 75, 89, 81, 81, 79, 63, 49, 49, 67, 115, 105, 105, 109, 127, 109, 105, 131, 139, 77, 81, 97, 65, 45, 75, 81, 69, 75, 79, 77, 83, 99, 105, 125, 111, 85, 117, 69, 61, 61, 67, 81, 51, 35, 89, 93, 107, 95, 71, 91, 85, 97, 137, 157, 157, 141, 169, 169, 177, 19, 13, 17, 5, 23, -9, -13, -11, -7, -13, -13, -35, 3, -1, 15, -5, 11, 5, 21, -3, -1, 21, 59, 63, 55, 49, 59, 63, 39, 35, 51, 23, 23, 15, 83, 89, 101, 83, 119, 119, 105, 119, 77, 83, 99, 109, 87, 87, 105, 105, 121, 87, 93, 89, 101, 121, 77, 79, 53, -11, 29, 81, 49, 49, 79, 55, 47, 51, 51, 41, 49, 57, 77, 47, 77, 83, 83, 81, 95, 87, 87, 85, 69, 55, 55, 73, 121, 111, 111, 115, 133, 115, 111, 137, 145, 65, 47, 61, 45, 91, 87, 55, 59, 65, 69, 67, 73, 89, 95, 115, 101, 75, 107, 59, 51, 51, 57, 71, 41, 25, 79, 83, 97, 85, 61, 81, 75, 87, 127, 147, 147, 131, 159, 159, 167, 9, 3, 7, -5, 13, -19, -23, -21, -17, -23, -23, -45, -7, -11, 5, -15, 1, -5, 11, -13, -11, 11, 49, 53, 45, 39, 49, 53, 29, 25, 41, 13, 13, 5, 73, 79, 91, 73, 109, 109, 95, 109, 67, 73, 89, 99, 77, 77, 95, 95, 111, 77, 83, 79, 91, 111, 67, 69, 43, -21, 19, 71, 39, 39, 69, 45, 37, 41, 41, 31, 39, 47, 67, 37, 67, 73, 73, 71, 85, 77, 77, 75, 59, 45, 45, 63, 111, 101, 101, 105, 123, 105, 101, 127, 135]
parities = [1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1]
# TODO: I ended up inlining this test, since it's probably more efficient to not pass all these lists around
# Either remove this, or make a more useful version that makes the binary-search code more readable...
# def checkoffset(targetpat, expectedoutcome, testglider, ticks):
# outcome = g.evolve(g.join(targetpat, testglider), ticks)
# return (str(outcome) == str(expectedoutcome)) # TODO: does it work without the str()? List comparisons can be weird.
g.new("Test salvo")
targetpat = g.parse("2o$2o!")
for item in zip(lanes, parities):
lane, parity = item
highdelta, lowdelta = INITIAL_DELTA, MIN_DELTA - 1 # we always know that the optimal glider position is somewhere between lowdelta and highdelta
# -- and when lowdelta and highdelta are the same value, we're done
# whatever happens when the glider is delayed by {delta} cells diagonally ...
# is what we want to be sure continues to happen in exactly the same way when we reduce the offset.
# So we'll start by defining the desired outcome to be whatever happens at the high end of the range.
#
# Let's say that the lowdelta variable will always contain the highest value that's known to not work
ticks = highdelta * 4 + LONG_ENOUGH
gliderpat = g.transform(EOlist[parity],(lane+1)//2+highdelta, highdelta)
expectedoutcome = g.evolve(g.join(targetpat, gliderpat), ticks)
while highdelta != lowdelta + 1:
newdelta = (lowdelta + 1 + highdelta) // 2 # bias toward the high side, since newdelta should never equal lowdelta
gliderpat = g.transform(EOlist[parity],(lane+1)//2+newdelta, newdelta)
outcome = g.evolve(g.join(targetpat, gliderpat), ticks)
if str(outcome)==str(expectedoutcome):
# the tested value is the new high value; rinse and repeat
g.putcells(outcome)
g.putcells(outcome)
g.fit()
g.update()
g.note("Still good at " + str(newdelta))
highdelta = newdelta
else:
# the tested value is the new low value; rinse and repeat
g.putcells(outcome)
g.fit()
g.update()
g.note("No good at " + str(newdelta))
lowdelta = newdelta
# We'll need a separate binary (?) search to determine how far we can advance the new targetpat+gliderpat pattern
# to produce a new targetpat and new expected outcome. It should be roughly the last tick before the
# gliderpat glider interacts with the previous targetpat -- but it can be a few ticks before that,
# if that makes it faster to check for the collision.
# Let's just try stepping forward by 16 ticks at a time and ensuring that the gliderpat is still the same shape,
# offset by 2N cells... but we won't worry about whether there are ON cells around the glider.
# I could imagine that there might be weird ways that this could cause optimization failures, but
# they would be very few and far between if we just stepped back to the previous 16-tick step before
# the final "passing" step.
offset += highdelta
# TODO: continue with next glider,
# but only after adjusting the target pattern until the current glider is almost ready to crash
# TODO: collect optimized recipe deltas, adjusting for the above adjustment!
g.exit()
EDIT: Here's a first attempt at getting through a complete optimization. It can be sped up a lot by removing the diagnostic g.new(), g.putcells(), g.fit() and g.update() commands:
Code: Select all
# new-binary-slow-salvo-optimizer.py
import golly as g
LONG_ENOUGH = 4096 # running each intermediate target plus a single glider for this long should produce the next intermediate target
MIN_DELTA = 5 # only optimize down to a safe distance (two blank lanes between adjacent slow gliders)
INITIAL_DELTA = MIN_DELTA + 256 # it should be safe (producing the desired output) to build the entire slow salvo at this offset
# the distance between min and initial might as well be a power of two, but it's not necessary
EOlist = [ g.parse("3o$o$bo!",-1,0), g.parse("bo$2o$obo!") ]
lanes = [9, 15, -1, 31, 19, -3, -5, 1, 5, 3, 9, 25, 31, 51, 37, 11, 43, -5, -13, -13, -7, 7, -23, -39, 15, 19, 33, 21, -3, 17, 11, 23, 63, 83, 83, 67, 95, 95, 103, -55, -61, -57, -69, -51, -83, -87, -85, -81, -87, -87, -109, -71, -75, -59, -79, -63, -69, -53, -77, -75, -53, -15, -11, -19, -25, -15, -11, -35, -39, -23, -51, -51, -59, 9, 15, 27, 9, 45, 45, 31, 45, 3, 9, 25, 35, 13, 13, 31, 31, 47, 13, 19, 15, 27, 47, 3, 5, -21, -85, -45, 7, -25, -25, 5, -19, -27, -23, -23, -33, -25, -17, 3, -27, 3, 9, 9, 7, 21, 13, 13, 11, -5, -19, -19, -1, 47, 37, 37, 41, 59, 41, 37, 63, 71, -9, -7, -3, -25, -13, -9, -15, -15, -13, -7, -3, -5, 1, 17, 23, 43, 29, 3, 35, -13, -21, -21, -15, -1, -31, -47, 7, 11, 25, 13, -11, 9, 3, 15, 55, 75, 75, 59, 87, 87, 95, -63, -69, -65, -77, -59, -91, -95, -93, -89, -95, -95, -117, -79, -83, -67, -87, -71, -77, -61, -85, -83, -61, -23, -19, -27, -33, -23, -19, -43, -47, -31, -59, -59, -67, 1, 7, 19, 1, 37, 37, 23, 37, -5, 1, 17, 27, 5, 5, 23, 23, 39, 5, 11, 7, 19, 39, -5, -3, -29, -93, -53, -1, -33, -33, -3, -27, -35, -31, -31, -41, -33, -25, -5, -35, -5, 1, 1, -1, 13, 5, 5, 3, -13, -27, -27, -9, 39, 29, 29, 33, 51, 33, 29, 55, 63, -17, -23, -7, -39, -27, -5, -21, -15, -11, -13, -7, 9, 15, 35, 21, -5, 27, -21, -29, -29, -23, -9, -39, -55, -1, 3, 17, 5, -19, 1, -5, 7, 47, 67, 67, 51, 79, 79, 87, -71, -77, -73, -85, -67, -99, -103, -101, -97, -103, -103, -125, -87, -91, -75, -95, -79, -85, -69, -93, -91, -69, -31, -27, -35, -41, -31, -27, -51, -55, -39, -67, -67, -75, -7, -1, 11, -7, 29, 29, 15, 29, -13, -7, 9, 19, -3, -3, 15, 15, 31, -3, 3, -1, 11, 31, -13, -11, -37, -101, -61, -9, -41, -41, -11, -35, -43, -39, -39, -49, -41, -33, -13, -43, -13, -7, -7, -9, 5, -3, -3, -5, -21, -35, -35, -17, 31, 21, 21, 25, 43, 25, 21, 47, 55, -7, -27, -9, -17, -13, -21, -37, -31, -31, -23, -53, -35, -29, -25, -27, -21, -5, 1, 21, 7, -19, 13, -35, -43, -43, -37, -23, -53, -69, -15, -11, 3, -9, -33, -13, -19, -7, 33, 53, 53, 37, 65, 65, 73, -85, -91, -87, -99, -81, -113, -117, -115, -111, -117, -117, -139, -101, -105, -89, -109, -93, -99, -83, -107, -105, -83, -45, -41, -49, -55, -45, -41, -65, -69, -53, -81, -81, -89, -21, -15, -3, -21, 15, 15, 1, 15, -27, -21, -5, 5, -17, -17, 1, 1, 17, -17, -11, -15, -3, 17, -27, -25, -51, -115, -75, -23, -55, -55, -25, -49, -57, -53, -53, -63, -55, -47, -27, -57, -27, -21, -21, -23, -9, -17, -17, -19, -35, -49, -49, -31, 17, 7, 7, 11, 29, 11, 7, 33, 41, -21, -3, -3, 5, -15, -15, -1, -19, -13, -9, -11, -5, 11, 17, 37, 23, -3, 29, -19, -27, -27, -21, -7, -37, -53, 1, 5, 19, 7, -17, 3, -3, 9, 49, 69, 69, 53, 81, 81, 89, -69, -75, -71, -83, -65, -97, -101, -99, -95, -101, -101, -123, -85, -89, -73, -93, -77, -83, -67, -91, -89, -67, -29, -25, -33, -39, -29, -25, -49, -53, -37, -65, -65, -73, -5, 1, 13, -5, 31, 31, 17, 31, -11, -5, 11, 21, -1, -1, 17, 17, 33, -1, 5, 1, 13, 33, -11, -9, -35, -99, -59, -7, -39, -39, -9, -33, -41, -37, -37, -47, -39, -31, -11, -41, -11, -5, -5, -7, 7, -1, -1, -3, -19, -33, -33, -15, 33, 23, 23, 27, 45, 27, 23, 49, 57, -23, -29, 1, 19, 5, -27, 13, -3, 3, 7, 5, 11, 27, 33, 53, 39, 13, 45, -3, -11, -11, -5, 9, -21, -37, 17, 21, 35, 23, -1, 19, 13, 25, 65, 85, 85, 69, 97, 97, 105, -53, -59, -55, -67, -49, -81, -85, -83, -79, -85, -85, -107, -69, -73, -57, -77, -61, -67, -51, -75, -73, -51, -13, -9, -17, -23, -13, -9, -33, -37, -21, -49, -49, -57, 11, 17, 29, 11, 47, 47, 33, 47, 5, 11, 27, 37, 15, 15, 33, 33, 49, 15, 21, 17, 29, 49, 5, 7, -19, -83, -43, 9, -23, -23, 7, -17, -25, -21, -21, -31, -23, -15, 5, -25, 5, 11, 11, 9, 23, 15, 15, 13, -3, -17, -17, 1, 49, 39, 39, 43, 61, 43, 39, 65, 73, 11, 17, 33, 11, 1, -31, -5, 1, 5, 3, 9, 25, 31, 51, 37, 11, 43, -5, -13, -13, -7, 7, -23, -39, 15, 19, 33, 21, -3, 17, 11, 23, 63, 83, 83, 67, 95, 95, 103, -55, -61, -57, -69, -51, -83, -87, -85, -81, -87, -87, -109, -71, -75, -59, -79, -63, -69, -53, -77, -75, -53, -15, -11, -19, -25, -15, -11, -35, -39, -23, -51, -51, -59, 9, 15, 27, 9, 45, 45, 31, 45, 3, 9, 25, 35, 13, 13, 31, 31, 47, 13, 19, 15, 27, 47, 3, 5, -21, -85, -45, 7, -25, -25, 5, -19, -27, -23, -23, -33, -25, -17, 3, -27, 3, 9, 9, 7, 21, 13, 13, 11, -5, -19, -19, -1, 47, 37, 37, 41, 59, 41, 37, 63, 71, -9, -3, 1, -9, -1, -7, -1, 3, 1, 7, 39, 23, 29, 49, 35, 9, 41, -7, -15, -15, -9, 5, -25, -41, 13, 17, 31, 19, -5, 15, 9, 21, 61, 81, 81, 65, 93, 93, 101, -57, -63, -59, -71, -53, -85, -89, -87, -83, -89, -89, -111, -73, -77, -61, -81, -65, -71, -55, -79, -77, -55, -17, -13, -21, -27, -17, -13, -37, -41, -25, -53, -53, -61, 7, 13, 25, 7, 43, 43, 29, 43, 1, 7, 23, 33, 11, 11, 29, 29, 45, 11, 17, 13, 25, 45, 1, 3, -23, -87, -47, 5, -27, -27, 3, -21, -29, -25, -25, -35, -27, -19, 1, -29, 1, 7, 7, 5, 19, 11, 11, 9, -7, -21, -21, -3, 45, 35, 35, 39, 57, 39, 35, 61, 69, -11, -5, -11, -19, -17, -13, -19, 7, -25, -45, -15, -9, -21, -15, -11, -13, -7, 9, 15, 35, 21, -5, 27, -21, -29, -29, -23, -9, -39, -55, -1, 3, 17, 5, -19, 1, -5, 7, 47, 67, 67, 51, 79, 79, 87, -71, -77, -73, -85, -67, -99, -103, -101, -97, -103, -103, -125, -87, -91, -75, -95, -79, -85, -69, -93, -91, -69, -31, -27, -35, -41, -31, -27, -51, -55, -39, -67, -67, -75, -7, -1, 11, -7, 29, 29, 15, 29, -13, -7, 9, 19, -3, -3, 15, 15, 31, -3, 3, -1, 11, 31, -13, -11, -37, -101, -61, -9, -41, -41, -11, -35, -43, -39, -39, -49, -41, -33, -13, -43, -13, -7, -7, -9, 5, -3, -3, -5, -21, -35, -35, -17, 31, 21, 21, 25, 43, 25, 21, 47, 55, -25, -19, -29, -45, -23, -27, -31, -25, -21, -23, -17, -1, 5, 25, 11, -15, 17, -31, -39, -39, -33, -19, -49, -65, -11, -7, 7, -5, -29, -9, -15, -3, 37, 57, 57, 41, 69, 69, 77, -81, -87, -83, -95, -77, -109, -113, -111, -107, -113, -113, -135, -97, -101, -85, -105, -89, -95, -79, -103, -101, -79, -41, -37, -45, -51, -41, -37, -61, -65, -49, -77, -77, -85, -17, -11, 1, -17, 19, 19, 5, 19, -23, -17, -1, 9, -13, -13, 5, 5, 21, -13, -7, -11, 1, 21, -23, -21, -47, -111, -71, -19, -51, -51, -21, -45, -53, -49, -49, -59, -51, -43, -23, -53, -23, -17, -17, -19, -5, -13, -13, -15, -31, -45, -45, -27, 21, 11, 11, 15, 33, 15, 11, 37, 45, -17, -13, -13, -17, -43, -21, -13, -15, -9, -5, -7, -1, 15, 21, 41, 27, 1, 33, -15, -23, -23, -17, -3, -33, -49, 5, 9, 23, 11, -13, 7, 1, 13, 53, 73, 73, 57, 85, 85, 93, -65, -71, -67, -79, -61, -93, -97, -95, -91, -97, -97, -119, -81, -85, -69, -89, -73, -79, -63, -87, -85, -63, -25, -21, -29, -35, -25, -21, -45, -49, -33, -61, -61, -69, -1, 5, 17, -1, 35, 35, 21, 35, -7, -1, 15, 25, 3, 3, 21, 21, 37, 3, 9, 5, 17, 37, -7, -5, -31, -95, -55, -3, -35, -35, -5, -29, -37, -33, -33, -43, -35, -27, -7, -37, -7, -1, -1, -3, 11, 3, 3, 1, -15, -29, -29, -11, 37, 27, 27, 31, 49, 31, 27, 53, 61, -19, -13, -23, -39, -17, -21, -25, -19, -15, -17, -11, 5, 11, 31, 17, -9, 23, -25, -33, -33, -27, -13, -43, -59, -5, -1, 13, 1, -23, -3, -9, 3, 43, 63, 63, 47, 75, 75, 83, -75, -81, -77, -89, -71, -103, -107, -105, -101, -107, -107, -129, -91, -95, -79, -99, -83, -89, -73, -97, -95, -73, -35, -31, -39, -45, -35, -31, -55, -59, -43, -71, -71, -79, -11, -5, 7, -11, 25, 25, 11, 25, -17, -11, 5, 15, -7, -7, 11, 11, 27, -7, -1, -5, 7, 27, -17, -15, -41, -105, -65, -13, -45, -45, -15, -39, -47, -43, -43, -53, -45, -37, -17, -47, -17, -11, -11, -13, 1, -7, -7, -9, -25, -39, -39, -21, 27, 17, 17, 21, 39, 21, 17, 43, 51, -11, -5, -21, 11, -1, -23, -25, -19, -15, -17, -11, 5, 11, 31, 17, -9, 23, -25, -33, -33, -27, -13, -43, -59, -5, -1, 13, 1, -23, -3, -9, 3, 43, 63, 63, 47, 75, 75, 83, -75, -81, -77, -89, -71, -103, -107, -105, -101, -107, -107, -129, -91, -95, -79, -99, -83, -89, -73, -97, -95, -73, -35, -31, -39, -45, -35, -31, -55, -59, -43, -71, -71, -79, -11, -5, 7, -11, 25, 25, 11, 25, -17, -11, 5, 15, -7, -7, 11, 11, 27, -7, -1, -5, 7, 27, -17, -15, -41, -105, -65, -13, -45, -45, -15, -39, -47, -43, -43, -53, -45, -37, -17, -47, -17, -11, -11, -13, 1, -7, -7, -9, -25, -39, -39, -21, 27, 17, 17, 21, 39, 21, 17, 43, 51, -11, -19, -35, -19, -9, -27, -9, -3, 1, -1, 5, 21, 27, 47, 33, 7, 39, -9, -17, -17, -11, 3, -27, -43, 11, 15, 29, 17, -7, 13, 7, 19, 59, 79, 79, 63, 91, 91, 99, -59, -65, -61, -73, -55, -87, -91, -89, -85, -91, -91, -113, -75, -79, -63, -83, -67, -73, -57, -81, -79, -57, -19, -15, -23, -29, -19, -15, -39, -43, -27, -55, -55, -63, 5, 11, 23, 5, 41, 41, 27, 41, -1, 5, 21, 31, 9, 9, 27, 27, 43, 9, 15, 11, 23, 43, -1, 1, -25, -89, -49, 3, -29, -29, 1, -23, -31, -27, -27, -37, -29, -21, -1, -31, -1, 5, 5, 3, 17, 9, 9, 7, -9, -23, -23, -5, 43, 33, 33, 37, 55, 37, 33, 59, 67, 5, 9, -5, 5, -3, -15, -9, -5, -7, -1, 15, 21, 41, 27, 1, 33, -15, -43, -23, -23, -17, -3, -33, -49, 5, 9, 23, 11, -13, 7, 1, 13, 53, 73, 73, 57, 85, 85, 93, -65, -71, -67, -79, -61, -93, -97, -95, -91, -97, -97, -119, -81, -85, -69, -89, -73, -79, -63, -87, -85, -63, -25, -21, -29, -35, -25, -21, -45, -49, -33, -61, -61, -69, -1, 5, 17, -1, 35, 35, 21, 35, -7, -1, 15, 25, 3, 3, 21, 21, 37, 3, 9, 5, 17, 37, -7, -5, -31, -95, -55, -3, -35, -35, -5, -29, -37, -33, -33, -43, -35, -27, -7, -37, -7, -1, -1, -3, 11, 3, 3, 1, -15, -29, -29, -11, 37, 27, 27, 31, 49, 31, 27, 53, 61, -1, 17, 3, -17, -1, -3, -1, 5, 9, 7, 13, 29, 35, 55, 41, 15, 47, -1, -9, -9, -3, 11, -19, -35, 19, 23, 37, 25, 1, 21, 15, 27, 67, 87, 87, 71, 99, 99, 107, -51, -57, -53, -65, -47, -79, -83, -81, -77, -83, -83, -105, -67, -71, -55, -75, -59, -65, -49, -73, -71, -49, -11, -7, -15, -21, -11, -7, -31, -35, -19, -47, -47, -55, 13, 19, 31, 13, 49, 49, 35, 49, 7, 13, 29, 39, 17, 17, 35, 35, 51, 17, 23, 19, 31, 51, 7, 9, -17, -81, -41, 11, -21, -21, 9, -15, -23, -19, -19, -29, -21, -13, 7, -23, 7, 13, 13, 11, 25, 17, 17, 15, -1, -15, -15, 3, 51, 41, 41, 45, 63, 45, 41, 67, 75, -5, -19, -3, 23, 33, 9, 15, 19, 17, 23, 39, 45, 65, 51, 25, 57, 9, 1, 1, 7, 21, -9, -25, 29, 33, 47, 35, 11, 31, 25, 37, 77, 97, 97, 81, 109, 109, 117, -41, -47, -43, -55, -37, -69, -73, -71, -67, -73, -73, -95, -57, -61, -45, -65, -49, -55, -39, -63, -61, -39, -1, 3, -5, -11, -1, 3, -21, -25, -9, -37, -37, -45, 23, 29, 41, 23, 59, 59, 45, 59, 17, 23, 39, 49, 27, 27, 45, 45, 61, 27, 33, 29, 41, 61, 17, 19, -7, -71, -31, 21, -11, -11, 19, -5, -13, -9, -9, -19, -11, -3, 17, -13, 17, 23, 23, 21, 35, 27, 27, 25, 9, -5, -5, 13, 61, 51, 51, 55, 73, 55, 51, 77, 85, 23, 27, 17, 11, 17, 9, 7, 13, 17, 15, 21, 37, 43, 63, 49, 23, 55, 7, -1, -1, 5, 19, -11, -27, 27, 31, 45, 33, 9, 29, 23, 35, 75, 95, 95, 79, 107, 107, 115, -43, -49, -45, -57, -39, -71, -75, -73, -69, -75, -75, -97, -59, -63, -47, -67, -51, -57, -41, -65, -63, -41, -3, 1, -7, -13, -3, 1, -23, -27, -11, -39, -39, -47, 21, 27, 39, 21, 57, 57, 43, 57, 15, 21, 37, 47, 25, 25, 43, 43, 59, 25, 31, 27, 39, 59, 15, 17, -9, -73, -33, 19, -13, -13, 17, -7, -15, -11, -11, -21, -13, -5, 15, -15, 15, 21, 21, 19, 33, 25, 25, 23, 7, -7, -7, 11, 59, 49, 49, 53, 71, 53, 49, 75, 83, 21, 13, -3, 13, 23, 5, 23, 29, 33, 31, 37, 53, 59, 79, 65, 39, 71, 23, 15, 15, 21, 35, 5, -11, 43, 47, 61, 49, 25, 45, 39, 51, 91, 111, 111, 95, 123, 123, 131, -27, -33, -29, -41, -23, -55, -59, -57, -53, -59, -59, -81, -43, -47, -31, -51, -35, -41, -25, -49, -47, -25, 13, 17, 9, 3, 13, 17, -7, -11, 5, -23, -23, -31, 37, 43, 55, 37, 73, 73, 59, 73, 31, 37, 53, 63, 41, 41, 59, 59, 75, 41, 47, 43, 55, 75, 31, 33, 7, -57, -17, 35, 3, 3, 33, 9, 1, 5, 5, -5, 3, 11, 31, 1, 31, 37, 37, 35, 49, 41, 41, 39, 23, 9, 9, 27, 75, 65, 65, 69, 87, 69, 65, 91, 99, 19, 25, 29, 19, 27, 21, 27, 31, 29, 35, 67, 51, 57, 77, 63, 37, 69, 21, 13, 13, 19, 33, 3, -13, 41, 45, 59, 47, 23, 43, 37, 49, 89, 109, 109, 93, 121, 121, 129, -29, -35, -31, -43, -25, -57, -61, -59, -55, -61, -61, -83, -45, -49, -33, -53, -37, -43, -27, -51, -49, -27, 11, 15, 7, 1, 11, 15, -9, -13, 3, -25, -25, -33, 35, 41, 53, 35, 71, 71, 57, 71, 29, 35, 51, 61, 39, 39, 57, 57, 73, 39, 45, 41, 53, 73, 29, 31, 5, -59, -19, 33, 1, 1, 31, 7, -1, 3, 3, -7, 1, 9, 29, -1, 29, 35, 35, 33, 47, 39, 39, 37, 21, 7, 7, 25, 73, 63, 63, 67, 85, 67, 63, 89, 97, 17, 23, 13, -3, 19, 21, 7, 13, 17, 15, 21, 37, 43, 63, 49, 23, 55, 7, -1, -1, 5, 19, -11, -27, 27, 31, 45, 33, 9, 29, 23, 35, 75, 95, 95, 79, 107, 107, 115, -43, -49, -45, -57, -39, -71, -75, -73, -69, -75, -75, -97, -59, -63, -47, -67, -51, -57, -41, -65, -63, -41, -3, 1, -7, -13, -3, 1, -23, -27, -11, -39, -39, -47, 21, 27, 39, 21, 57, 57, 43, 57, 15, 21, 37, 47, 25, 25, 43, 43, 59, 25, 31, 27, 39, 59, 15, 17, -9, -73, -33, 19, -13, -13, 17, -7, -15, -11, -11, -21, -13, -5, 15, -15, 15, 21, 21, 19, 33, 25, 25, 23, 7, -7, -7, 11, 59, 49, 49, 53, 71, 53, 49, 75, 83, 21, 25, 15, -1, 21, 17, 13, 19, 23, 21, 27, 43, 49, 69, 55, 29, 61, 13, 5, 5, 11, 25, -5, -21, 33, 37, 51, 39, 15, 35, 29, 41, 81, 101, 101, 85, 113, 113, 121, -37, -43, -39, -51, -33, -65, -69, -67, -63, -69, -69, -91, -53, -57, -41, -61, -45, -51, -35, -59, -57, -35, 3, 7, -1, -7, 3, 7, -17, -21, -5, -33, -33, -41, 27, 33, 45, 27, 63, 63, 49, 63, 21, 27, 43, 53, 31, 31, 49, 49, 65, 31, 37, 33, 45, 65, 21, 23, -3, -67, -27, 25, -7, -7, 23, -1, -9, -5, -5, -15, -7, 1, 21, -9, 21, 27, 27, 25, 39, 31, 31, 29, 13, -1, -1, 17, 65, 55, 55, 59, 77, 59, 55, 81, 89, 27, 31, 21, 5, 27, 29, 15, 21, 25, 23, 29, 45, 51, 71, 57, 31, 63, 15, 7, 7, 13, 27, -3, -19, 35, 39, 53, 41, 17, 37, 31, 43, 83, 103, 103, 87, 115, 115, 123, -35, -41, -37, -49, -31, -63, -67, -65, -61, -67, -67, -89, -51, -55, -39, -59, -43, -49, -33, -57, -55, -33, 5, 9, 1, -5, 5, 9, -15, -19, -3, -31, -31, -39, 29, 35, 47, 29, 65, 65, 51, 65, 23, 29, 45, 55, 33, 33, 51, 51, 67, 33, 39, 35, 47, 67, 23, 25, -1, -65, -25, 27, -5, -5, 25, 1, -7, -3, -3, -13, -5, 3, 23, -7, 23, 29, 29, 27, 41, 33, 33, 31, 15, 1, 1, 19, 67, 57, 57, 61, 79, 61, 57, 83, 91, 29, 47, 33, 13, 29, 35, 21, 27, 31, 29, 35, 51, 57, 77, 63, 37, 69, 21, 13, 13, 19, 33, 3, -13, 41, 45, 59, 47, 23, 43, 37, 49, 89, 109, 109, 93, 121, 121, 129, -29, -35, -31, -43, -25, -57, -61, -59, -55, -61, -61, -83, -45, -49, -33, -53, -37, -43, -27, -51, -49, -27, 11, 15, 7, 1, 11, 15, -9, -13, 3, -25, -25, -33, 35, 41, 53, 35, 71, 71, 57, 71, 29, 35, 51, 61, 39, 39, 57, 57, 73, 39, 45, 41, 53, 73, 29, 31, 5, -59, -19, 33, 1, 1, 31, 7, -1, 3, 3, -7, 1, 9, 29, -1, 29, 35, 35, 33, 47, 39, 39, 37, 21, 7, 7, 25, 73, 63, 63, 67, 85, 67, 63, 89, 97, 17, 3, 27, 21, 25, 45, 31, 37, 41, 39, 45, 61, 67, 87, 73, 47, 79, 31, 23, 23, 29, 43, 13, -3, 51, 55, 69, 57, 33, 53, 47, 59, 99, 119, 119, 103, 131, 131, 139, -19, -25, -21, -33, -15, -47, -51, -49, -45, -51, -51, -73, -35, -39, -23, -43, -27, -33, -17, -41, -39, -17, 21, 25, 17, 11, 21, 25, 1, -3, 13, -15, -15, -23, 45, 51, 63, 45, 81, 81, 67, 81, 39, 45, 61, 71, 49, 49, 67, 67, 83, 49, 55, 51, 63, 83, 39, 41, 15, -49, -9, 43, 11, 11, 41, 17, 9, 13, 13, 3, 11, 19, 39, 9, 39, 45, 45, 43, 57, 49, 49, 47, 31, 17, 17, 35, 83, 73, 73, 77, 95, 77, 73, 99, 107, 27, 27, 25, 19, 17, 15, 37, 43, 47, 45, 51, 67, 73, 93, 79, 53, 85, 37, 29, 29, 35, 49, 19, 3, 57, 61, 75, 63, 39, 59, 53, 65, 105, 125, 125, 109, 137, 137, 145, -13, -19, -15, -27, -9, -41, -45, -43, -39, -45, -45, -67, -29, -33, -17, -37, -21, -27, -11, -35, -33, -11, 27, 31, 23, 17, 27, 31, 7, 3, 19, -9, -9, -17, 51, 57, 69, 51, 87, 87, 73, 87, 45, 51, 67, 77, 55, 55, 73, 73, 89, 55, 61, 57, 69, 89, 45, 47, 21, -43, -3, 49, 17, 17, 47, 23, 15, 19, 19, 9, 17, 25, 45, 15, 45, 51, 51, 49, 63, 55, 55, 53, 37, 23, 23, 41, 89, 79, 79, 83, 101, 83, 79, 105, 113, 33, 15, 29, 49, 33, 27, 23, 29, 33, 31, 37, 53, 59, 79, 65, 39, 71, 23, 15, 15, 21, 35, 5, -11, 43, 47, 61, 49, 25, 45, 39, 51, 91, 111, 111, 95, 123, 123, 131, -27, -33, -29, -41, -23, -55, -59, -57, -53, -59, -59, -81, -43, -47, -31, -51, -35, -41, -25, -49, -47, -25, 13, 17, 9, 3, 13, 17, -7, -11, 5, -23, -23, -31, 37, 43, 55, 37, 73, 73, 59, 73, 31, 37, 53, 63, 41, 41, 59, 59, 75, 41, 47, 43, 55, 75, 31, 33, 7, -57, -17, 35, 3, 3, 33, 9, 1, 5, 5, -5, 3, 11, 31, 1, 31, 37, 37, 35, 49, 41, 41, 39, 23, 9, 9, 27, 75, 65, 65, 69, 87, 69, 65, 91, 99, 19, 13, -7, 9, -1, 43, 27, 33, 37, 35, 41, 57, 63, 83, 69, 43, 75, 27, 19, 19, 25, 39, 9, -7, 47, 51, 65, 53, 29, 49, 43, 55, 95, 115, 115, 99, 127, 127, 135, -23, -29, -25, -37, -19, -51, -55, -53, -49, -55, -55, -77, -39, -43, -27, -47, -31, -37, -21, -45, -43, -21, 17, 21, 13, 7, 17, 21, -3, -7, 9, -19, -19, -27, 41, 47, 59, 41, 77, 77, 63, 77, 35, 41, 57, 67, 45, 45, 63, 63, 79, 45, 51, 47, 59, 79, 35, 37, 11, -53, -13, 39, 7, 7, 37, 13, 5, 9, 9, -1, 7, 15, 35, 5, 35, 41, 41, 39, 53, 45, 45, 43, 27, 13, 13, 31, 79, 69, 69, 73, 91, 73, 69, 95, 103, 41, 21, 21, 13, 19, 19, 15, 21, 25, 23, 29, 45, 51, 71, 57, 31, 63, 15, 7, 7, 13, 27, -3, -19, 35, 39, 53, 41, 17, 37, 31, 43, 83, 103, 103, 87, 115, 115, 123, -35, -41, -37, -49, -31, -63, -67, -65, -61, -67, -67, -89, -51, -55, -39, -59, -43, -49, -33, -57, -55, -33, 5, 9, 1, -5, 5, 9, -15, -19, -3, -31, -31, -39, 29, 35, 47, 29, 65, 65, 51, 65, 23, 29, 45, 55, 33, 33, 51, 51, 67, 33, 39, 35, 47, 67, 23, 25, -1, -65, -25, 27, -5, -5, 25, 1, -7, -3, -3, -13, -5, 3, 23, -7, 23, 29, 29, 27, 41, 33, 33, 31, 15, 1, 1, 19, 67, 57, 57, 61, 79, 61, 57, 83, 91, 29, 33, 23, 39, 55, 29, 43, 1, 7, 11, 9, 15, 31, 37, 57, 43, 17, 49, 1, -7, -7, -1, 13, -17, -33, 21, 25, 39, 27, 3, 23, 17, 29, 69, 89, 89, 73, 101, 101, 109, -49, -55, -51, -63, -45, -77, -81, -79, -75, -81, -81, -103, -65, -69, -53, -73, -57, -63, -47, -71, -69, -47, -9, -5, -13, -19, -9, -5, -29, -33, -17, -45, -45, -53, 15, 21, 33, 15, 51, 51, 37, 51, 9, 15, 31, 41, 19, 19, 37, 37, 53, 19, 25, 21, 33, 53, 9, 11, -15, -79, -39, 13, -19, -19, 11, -13, -21, -17, -17, -27, -19, -11, 9, -21, 9, 15, 15, 13, 27, 19, 19, 17, 1, -13, -13, 5, 53, 43, 43, 47, 65, 47, 43, 69, 77, -3, -17, 7, 1, 5, 25, 11, 17, 21, 19, 25, 41, 47, 67, 53, 27, 59, 11, 3, 3, 9, 23, -7, -23, 31, 35, 49, 37, 13, 33, 27, 39, 79, 99, 99, 83, 111, 111, 119, -39, -45, -41, -53, -35, -67, -71, -69, -65, -71, -71, -93, -55, -59, -43, -63, -47, -53, -37, -61, -59, -37, 1, 5, -3, -9, 1, 5, -19, -23, -7, -35, -35, -43, 25, 31, 43, 25, 61, 61, 47, 61, 19, 25, 41, 51, 29, 29, 47, 47, 63, 29, 35, 31, 43, 63, 19, 21, -5, -69, -29, 23, -9, -9, 21, -3, -11, -7, -7, -17, -9, -1, 19, -11, 19, 25, 25, 23, 37, 29, 29, 27, 11, -3, -3, 15, 63, 53, 53, 57, 75, 57, 53, 79, 87, 25, 29, 15, 25, 17, 5, 11, 15, 13, 19, 35, 41, 61, 47, 21, 53, 5, -23, -3, -3, 3, 17, -13, -29, 25, 29, 43, 31, 7, 27, 21, 33, 73, 93, 93, 77, 105, 105, 113, -45, -51, -47, -59, -41, -73, -77, -75, -71, -77, -77, -99, -61, -65, -49, -69, -53, -59, -43, -67, -65, -43, -5, -1, -9, -15, -5, -1, -25, -29, -13, -41, -41, -49, 19, 25, 37, 19, 55, 55, 41, 55, 13, 19, 35, 45, 23, 23, 41, 41, 57, 23, 29, 25, 37, 57, 13, 15, -11, -75, -35, 17, -15, -15, 15, -9, -17, -13, -13, -23, -15, -7, 13, -17, 13, 19, 19, 17, 31, 23, 23, 21, 5, -9, -9, 9, 57, 47, 47, 51, 69, 51, 47, 73, 81, 19, 23, 13, -3, 19, 15, 11, 17, 21, 19, 25, 41, 47, 67, 53, 27, 59, 11, 3, 3, 9, 23, -7, -23, 31, 35, 49, 37, 13, 33, 27, 39, 79, 99, 99, 83, 111, 111, 119, -39, -45, -41, -53, -35, -67, -71, -69, -65, -71, -71, -93, -55, -59, -43, -63, -47, -53, -37, -61, -59, -37, 1, 5, -3, -9, 1, 5, -19, -23, -7, -35, -35, -43, 25, 31, 43, 25, 61, 61, 47, 61, 19, 25, 41, 51, 29, 29, 47, 47, 63, 29, 35, 31, 43, 63, 19, 21, -5, -69, -29, 23, -9, -9, 21, -3, -11, -7, -7, -17, -9, -1, 19, -11, 19, 25, 25, 23, 37, 29, 29, 27, 11, -3, -3, 15, 63, 53, 53, 57, 75, 57, 53, 79, 87, 7, 13, 17, 7, 15, 9, 15, 19, 17, 23, 55, 39, 45, 65, 51, 25, 57, 9, 1, 1, 7, 21, -9, -25, 29, 33, 47, 35, 11, 31, 25, 37, 77, 97, 97, 81, 109, 109, 117, -41, -47, -43, -55, -37, -69, -73, -71, -67, -73, -73, -95, -57, -61, -45, -65, -49, -55, -39, -63, -61, -39, -1, 3, -5, -11, -1, 3, -21, -25, -9, -37, -37, -45, 23, 29, 41, 23, 59, 59, 45, 59, 17, 23, 39, 49, 27, 27, 45, 45, 61, 27, 33, 29, 41, 61, 17, 19, -7, -71, -31, 21, -11, -11, 19, -5, -13, -9, -9, -19, -11, -3, 17, -13, 17, 23, 23, 21, 35, 27, 27, 25, 9, -5, -5, 13, 61, 51, 51, 55, 73, 55, 51, 77, 85, 5, -1, -21, -5, -15, 29, 13, 19, 23, 21, 27, 43, 49, 69, 55, 29, 61, 13, 5, 5, 11, 25, -5, -21, 33, 37, 51, 39, 15, 35, 29, 41, 81, 101, 101, 85, 113, 113, 121, -37, -43, -39, -51, -33, -65, -69, -67, -63, -69, -69, -91, -53, -57, -41, -61, -45, -51, -35, -59, -57, -35, 3, 7, -1, -7, 3, 7, -17, -21, -5, -33, -33, -41, 27, 33, 45, 27, 63, 63, 49, 63, 21, 27, 43, 53, 31, 31, 49, 49, 65, 31, 37, 33, 45, 65, 21, 23, -3, -67, -27, 25, -7, -7, 23, -1, -9, -5, -5, -15, -7, 1, 21, -9, 21, 27, 27, 25, 39, 31, 31, 29, 13, -1, -1, 17, 65, 55, 55, 59, 77, 59, 55, 81, 89, 9, -5, 19, 13, 17, 37, 23, 29, 33, 31, 37, 53, 59, 79, 65, 39, 71, 23, 15, 15, 21, 35, 5, -11, 43, 47, 61, 49, 25, 45, 39, 51, 91, 111, 111, 95, 123, 123, 131, -27, -33, -29, -41, -23, -55, -59, -57, -53, -59, -59, -81, -43, -47, -31, -51, -35, -41, -25, -49, -47, -25, 13, 17, 9, 3, 13, 17, -7, -11, 5, -23, -23, -31, 37, 43, 55, 37, 73, 73, 59, 73, 31, 37, 53, 63, 41, 41, 59, 59, 75, 41, 47, 43, 55, 75, 31, 33, 7, -57, -17, 35, 3, 3, 33, 9, 1, 5, 5, -5, 3, 11, 31, 1, 31, 37, 37, 35, 49, 41, 41, 39, 23, 9, 9, 27, 75, 65, 65, 69, 87, 69, 65, 91, 99, 37, 41, 31, 15, 37, 39, 25, 31, 35, 33, 39, 55, 61, 81, 67, 41, 73, 25, 17, 17, 23, 37, 7, -9, 45, 49, 63, 51, 27, 47, 41, 53, 93, 113, 113, 97, 125, 125, 133, -25, -31, -27, -39, -21, -53, -57, -55, -51, -57, -57, -79, -41, -45, -29, -49, -33, -39, -23, -47, -45, -23, 15, 19, 11, 5, 15, 19, -5, -9, 7, -21, -21, -29, 39, 45, 57, 39, 75, 75, 61, 75, 33, 39, 55, 65, 43, 43, 61, 61, 77, 43, 49, 45, 57, 77, 33, 35, 9, -55, -15, 37, 5, 5, 35, 11, 3, 7, 7, -3, 5, 13, 33, 3, 33, 39, 39, 37, 51, 43, 43, 41, 25, 11, 11, 29, 77, 67, 67, 71, 89, 71, 67, 93, 101, 39, 43, 29, 39, 31, 19, 25, 29, 27, 33, 49, 55, 75, 61, 35, 67, 19, -9, 11, 11, 17, 31, 1, -15, 39, 43, 57, 45, 21, 41, 35, 47, 87, 107, 107, 91, 119, 119, 127, -31, -37, -33, -45, -27, -59, -63, -61, -57, -63, -63, -85, -47, -51, -35, -55, -39, -45, -29, -53, -51, -29, 9, 13, 5, -1, 9, 13, -11, -15, 1, -27, -27, -35, 33, 39, 51, 33, 69, 69, 55, 69, 27, 33, 49, 59, 37, 37, 55, 55, 71, 37, 43, 39, 51, 71, 27, 29, 3, -61, -21, 31, -1, -1, 29, 5, -3, 1, 1, -9, -1, 7, 27, -3, 27, 33, 33, 31, 45, 37, 37, 35, 19, 5, 5, 23, 71, 61, 61, 65, 83, 65, 61, 87, 95, 33, 37, 27, 11, 33, 35, 21, 27, 31, 29, 35, 51, 57, 77, 63, 37, 69, 21, 13, 13, 19, 33, 3, -13, 41, 45, 59, 47, 23, 43, 37, 49, 89, 109, 109, 93, 121, 121, 129, -29, -35, -31, -43, -25, -57, -61, -59, -55, -61, -61, -83, -45, -49, -33, -53, -37, -43, -27, -51, -49, -27, 11, 15, 7, 1, 11, 15, -9, -13, 3, -25, -25, -33, 35, 41, 53, 35, 71, 71, 57, 71, 29, 35, 51, 61, 39, 39, 57, 57, 73, 39, 45, 41, 53, 73, 29, 31, 5, -59, -19, 33, 1, 1, 31, 7, -1, 3, 3, -7, 1, 9, 29, -1, 29, 35, 35, 33, 47, 39, 39, 37, 21, 7, 7, 25, 73, 63, 63, 67, 85, 67, 63, 89, 97, 17, 23, 27, 17, 25, 19, 25, 29, 27, 33, 65, 49, 55, 75, 61, 35, 67, 19, 11, 11, 17, 31, 1, -15, 39, 43, 57, 45, 21, 41, 35, 47, 87, 107, 107, 91, 119, 119, 127, -31, -37, -33, -45, -27, -59, -63, -61, -57, -63, -63, -85, -47, -51, -35, -55, -39, -45, -29, -53, -51, -29, 9, 13, 5, -1, 9, 13, -11, -15, 1, -27, -27, -35, 33, 39, 51, 33, 69, 69, 55, 69, 27, 33, 49, 59, 37, 37, 55, 55, 71, 37, 43, 39, 51, 71, 27, 29, 3, -61, -21, 31, -1, -1, 29, 5, -3, 1, 1, -9, -1, 7, 27, -3, 27, 33, 33, 31, 45, 37, 37, 35, 19, 5, 5, 23, 71, 61, 61, 65, 83, 65, 61, 87, 95, 33, 17, 31, 1, 43, 61, 49, 33, 39, 43, 41, 47, 63, 69, 89, 75, 49, 81, 33, 25, 25, 31, 45, 15, -1, 53, 57, 71, 59, 35, 55, 49, 61, 101, 121, 121, 105, 133, 133, 141, -17, -23, -19, -31, -13, -45, -49, -47, -43, -49, -49, -71, -33, -37, -21, -41, -25, -31, -15, -39, -37, -15, 23, 27, 19, 13, 23, 27, 3, -1, 15, -13, -13, -21, 47, 53, 65, 47, 83, 83, 69, 83, 41, 47, 63, 73, 51, 51, 69, 69, 85, 51, 57, 53, 65, 85, 41, 43, 17, -47, -7, 45, 13, 13, 43, 19, 11, 15, 15, 5, 13, 21, 41, 11, 41, 47, 47, 45, 59, 51, 51, 49, 33, 19, 19, 37, 85, 75, 75, 79, 97, 79, 75, 101, 109, 47, 27, 27, 19, 25, 25, 21, 27, 31, 29, 35, 51, 57, 77, 63, 37, 69, 21, 13, 13, 19, 33, 3, -13, 41, 45, 59, 47, 23, 43, 37, 49, 89, 109, 109, 93, 121, 121, 129, -29, -35, -31, -43, -25, -57, -61, -59, -55, -61, -61, -83, -45, -49, -33, -53, -37, -43, -27, -51, -49, -27, 11, 15, 7, 1, 11, 15, -9, -13, 3, -25, -25, -33, 35, 41, 53, 35, 71, 71, 57, 71, 29, 35, 51, 61, 39, 39, 57, 57, 73, 39, 45, 41, 53, 73, 29, 31, 5, -59, -19, 33, 1, 1, 31, 7, -1, 3, 3, -7, 1, 9, 29, -1, 29, 35, 35, 33, 47, 39, 39, 37, 21, 7, 7, 25, 73, 63, 63, 67, 85, 67, 63, 89, 97, 17, 23, 27, 17, 25, 19, 25, 29, 27, 33, 65, 49, 55, 75, 61, 35, 67, 19, 11, 11, 17, 31, 1, -15, 39, 43, 57, 45, 21, 41, 35, 47, 87, 107, 107, 91, 119, 119, 127, -31, -37, -33, -45, -27, -59, -63, -61, -57, -63, -63, -85, -47, -51, -35, -55, -39, -45, -29, -53, -51, -29, 9, 13, 5, -1, 9, 13, -11, -15, 1, -27, -27, -35, 33, 39, 51, 33, 69, 69, 55, 69, 27, 33, 49, 59, 37, 37, 55, 55, 71, 37, 43, 39, 51, 71, 27, 29, 3, -61, -21, 31, -1, -1, 29, 5, -3, 1, 1, -9, -1, 7, 27, -3, 27, 33, 33, 31, 45, 37, 37, 35, 19, 5, 5, 23, 71, 61, 61, 65, 83, 65, 61, 87, 95, 15, 9, -11, 5, -5, 39, 23, 29, 33, 31, 37, 53, 59, 79, 65, 39, 71, 23, 15, 15, 21, 35, 5, -11, 43, 47, 61, 49, 25, 45, 39, 51, 91, 111, 111, 95, 123, 123, 131, -27, -33, -29, -41, -23, -55, -59, -57, -53, -59, -59, -81, -43, -47, -31, -51, -35, -41, -25, -49, -47, -25, 13, 17, 9, 3, 13, 17, -7, -11, 5, -23, -23, -31, 37, 43, 55, 37, 73, 73, 59, 73, 31, 37, 53, 63, 41, 41, 59, 59, 75, 41, 47, 43, 55, 75, 31, 33, 7, -57, -17, 35, 3, 3, 33, 9, 1, 5, 5, -5, 3, 11, 31, 1, 31, 37, 37, 35, 49, 41, 41, 39, 23, 9, 9, 27, 75, 65, 65, 69, 87, 69, 65, 91, 99, 37, 41, 27, 37, 29, 17, 23, 27, 25, 31, 47, 53, 73, 59, 33, 65, 17, -11, 9, 9, 15, 29, -1, -17, 37, 41, 55, 43, 19, 39, 33, 45, 85, 105, 105, 89, 117, 117, 125, -33, -39, -35, -47, -29, -61, -65, -63, -59, -65, -65, -87, -49, -53, -37, -57, -41, -47, -31, -55, -53, -31, 7, 11, 3, -3, 7, 11, -13, -17, -1, -29, -29, -37, 31, 37, 49, 31, 67, 67, 53, 67, 25, 31, 47, 57, 35, 35, 53, 53, 69, 35, 41, 37, 49, 69, 25, 27, 1, -63, -23, 29, -3, -3, 27, 3, -5, -1, -1, -11, -3, 5, 25, -5, 25, 31, 31, 29, 43, 35, 35, 33, 17, 3, 3, 21, 69, 59, 59, 63, 81, 63, 59, 85, 93, 31, 35, 25, 15, 29, 3, 29, 35, 39, 37, 43, 59, 65, 85, 71, 45, 77, 29, 21, 21, 27, 41, 11, -5, 49, 53, 67, 55, 31, 51, 45, 57, 97, 117, 117, 101, 129, 129, 137, -21, -27, -23, -35, -17, -49, -53, -51, -47, -53, -53, -75, -37, -41, -25, -45, -29, -35, -19, -43, -41, -19, 19, 23, 15, 9, 19, 23, -1, -5, 11, -17, -17, -25, 43, 49, 61, 43, 79, 79, 65, 79, 37, 43, 59, 69, 47, 47, 65, 65, 81, 47, 53, 49, 61, 81, 37, 39, 13, -51, -11, 41, 9, 9, 39, 15, 7, 11, 11, 1, 9, 17, 37, 7, 37, 43, 43, 41, 55, 47, 47, 45, 29, 15, 15, 33, 81, 71, 71, 75, 93, 75, 71, 97, 105, 43, 47, 37, 21, 43, 39, 35, 41, 45, 43, 49, 65, 71, 91, 77, 51, 83, 35, 27, 27, 33, 47, 17, 1, 55, 59, 73, 61, 37, 57, 51, 63, 103, 123, 123, 107, 135, 135, 143, -15, -21, -17, -29, -11, -43, -47, -45, -41, -47, -47, -69, -31, -35, -19, -39, -23, -29, -13, -37, -35, -13, 25, 29, 21, 15, 25, 29, 5, 1, 17, -11, -11, -19, 49, 55, 67, 49, 85, 85, 71, 85, 43, 49, 65, 75, 53, 53, 71, 71, 87, 53, 59, 55, 67, 87, 43, 45, 19, -45, -5, 47, 15, 15, 45, 21, 13, 17, 17, 7, 15, 23, 43, 13, 43, 49, 49, 47, 61, 53, 53, 51, 35, 21, 21, 39, 87, 77, 77, 81, 99, 81, 77, 103, 111, 31, 17, 41, 35, 39, 53, 49, 55, 59, 57, 63, 79, 85, 105, 91, 65, 97, 49, 41, 41, 47, 61, 31, 15, 69, 73, 87, 75, 51, 71, 65, 77, 117, 137, 137, 121, 149, 149, 157, -1, -7, -3, -15, 3, -29, -33, -31, -27, -33, -33, -55, -17, -21, -5, -25, -9, -15, 1, -23, -21, 1, 39, 43, 35, 29, 39, 43, 19, 15, 31, 3, 3, -5, 63, 69, 81, 63, 99, 99, 85, 99, 57, 63, 79, 89, 67, 67, 85, 85, 101, 67, 73, 69, 81, 101, 57, 59, 33, -31, 9, 61, 29, 29, 59, 35, 27, 31, 31, 21, 29, 37, 57, 27, 57, 63, 63, 61, 75, 67, 67, 65, 49, 35, 35, 53, 101, 91, 91, 95, 113, 95, 91, 117, 125, 63, 67, 57, 41, 63, 65, 51, 57, 61, 59, 65, 81, 87, 107, 93, 67, 99, 51, 43, 43, 49, 63, 33, 17, 71, 75, 89, 77, 53, 73, 67, 79, 119, 139, 139, 123, 151, 151, 159, 1, -5, -1, -13, 5, -27, -31, -29, -25, -31, -31, -53, -15, -19, -3, -23, -7, -13, 3, -21, -19, 3, 41, 45, 37, 31, 41, 45, 21, 17, 33, 5, 5, -3, 65, 71, 83, 65, 101, 101, 87, 101, 59, 65, 81, 91, 69, 69, 87, 87, 103, 69, 75, 71, 83, 103, 59, 61, 35, -29, 11, 63, 31, 31, 61, 37, 29, 33, 33, 23, 31, 39, 59, 29, 59, 65, 65, 63, 77, 69, 69, 67, 51, 37, 37, 55, 103, 93, 93, 97, 115, 97, 93, 119, 127, 65, 69, 63, 73, 65, 55, 47, 45, 51, 55, 53, 59, 75, 81, 101, 87, 61, 93, 45, 37, 37, 43, 57, 27, 11, 65, 69, 83, 71, 47, 67, 61, 73, 113, 133, 133, 117, 145, 145, 153, -5, -11, -7, -19, -1, -33, -37, -35, -31, -37, -37, -59, -21, -25, -9, -29, -13, -19, -3, -27, -25, -3, 35, 39, 31, 25, 35, 39, 15, 11, 27, -1, -1, -9, 59, 65, 77, 59, 95, 95, 81, 95, 53, 59, 75, 85, 63, 63, 81, 81, 97, 63, 69, 65, 77, 97, 53, 55, 29, -35, 5, 57, 25, 25, 55, 31, 23, 27, 27, 17, 25, 33, 53, 23, 53, 59, 59, 57, 71, 63, 63, 61, 45, 31, 31, 49, 97, 87, 87, 91, 109, 91, 87, 113, 121, 41, 47, 41, 51, 49, 59, 67, 51, 57, 61, 59, 65, 81, 87, 107, 93, 67, 99, 51, 43, 43, 49, 63, 33, 17, 71, 75, 89, 77, 53, 73, 67, 79, 119, 139, 139, 123, 151, 151, 159, 1, -5, -1, -13, 5, -27, -31, -29, -25, -31, -31, -53, -15, -19, -3, -23, -7, -13, 3, -21, -19, 3, 41, 45, 37, 31, 41, 45, 21, 17, 33, 5, 5, -3, 65, 71, 83, 65, 101, 101, 87, 101, 59, 65, 81, 91, 69, 69, 87, 87, 103, 69, 75, 71, 83, 103, 59, 61, 35, -29, 11, 63, 31, 31, 61, 37, 29, 33, 33, 23, 31, 39, 59, 29, 59, 65, 65, 63, 77, 69, 69, 67, 51, 37, 37, 55, 103, 93, 93, 97, 115, 97, 93, 119, 127, 47, 53, 43, 49, 57, 47, 63, 69, 73, 71, 77, 93, 99, 119, 105, 79, 111, 63, 55, 55, 61, 75, 45, 29, 83, 87, 101, 89, 65, 85, 79, 91, 131, 151, 151, 135, 163, 163, 171, 13, 7, 11, -1, 17, -15, -19, -17, -13, -19, -19, -41, -3, -7, 9, -11, 5, -1, 15, -9, -7, 15, 53, 57, 49, 43, 53, 57, 33, 29, 45, 17, 17, 9, 77, 83, 95, 77, 113, 113, 99, 113, 71, 77, 93, 103, 81, 81, 99, 99, 115, 81, 87, 83, 95, 115, 71, 73, 47, -17, 23, 75, 43, 43, 73, 49, 41, 45, 45, 35, 43, 51, 71, 41, 71, 77, 77, 75, 89, 81, 81, 79, 63, 49, 49, 67, 115, 105, 105, 109, 127, 109, 105, 131, 139, 77, 81, 97, 65, 45, 75, 81, 69, 75, 79, 77, 83, 99, 105, 125, 111, 85, 117, 69, 61, 61, 67, 81, 51, 35, 89, 93, 107, 95, 71, 91, 85, 97, 137, 157, 157, 141, 169, 169, 177, 19, 13, 17, 5, 23, -9, -13, -11, -7, -13, -13, -35, 3, -1, 15, -5, 11, 5, 21, -3, -1, 21, 59, 63, 55, 49, 59, 63, 39, 35, 51, 23, 23, 15, 83, 89, 101, 83, 119, 119, 105, 119, 77, 83, 99, 109, 87, 87, 105, 105, 121, 87, 93, 89, 101, 121, 77, 79, 53, -11, 29, 81, 49, 49, 79, 55, 47, 51, 51, 41, 49, 57, 77, 47, 77, 83, 83, 81, 95, 87, 87, 85, 69, 55, 55, 73, 121, 111, 111, 115, 133, 115, 111, 137, 145, 65, 47, 61, 45, 91, 87, 55, 59, 65, 69, 67, 73, 89, 95, 115, 101, 75, 107, 59, 51, 51, 57, 71, 41, 25, 79, 83, 97, 85, 61, 81, 75, 87, 127, 147, 147, 131, 159, 159, 167, 9, 3, 7, -5, 13, -19, -23, -21, -17, -23, -23, -45, -7, -11, 5, -15, 1, -5, 11, -13, -11, 11, 49, 53, 45, 39, 49, 53, 29, 25, 41, 13, 13, 5, 73, 79, 91, 73, 109, 109, 95, 109, 67, 73, 89, 99, 77, 77, 95, 95, 111, 77, 83, 79, 91, 111, 67, 69, 43, -21, 19, 71, 39, 39, 69, 45, 37, 41, 41, 31, 39, 47, 67, 37, 67, 73, 73, 71, 85, 77, 77, 75, 59, 45, 45, 63, 111, 101, 101, 105, 123, 105, 101, 127, 135]
parities = [1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1]
reverse_salvo = -1
def checkoffset(targetpat, expectedoutcome, testglider, ticks):
outcome = g.evolve(g.join(targetpat, testglider), ticks)
return (str(outcome) == str(expectedoutcome)) # TODO: does it work without the str()? List comparisons can be weird.
targetpat = g.parse("2o$2o!")
targetpat = g.parse("""814b2o$814b2o11$805b2o$805b2o8b2o$814bo2bo$815b2o4bo$820bobo$820bobo$
821bo7$806b2o$805bo2bo$806b2o4bo$811bobo$811bobo$812bo3$824b2o$823bo2b
o$824b2o3$786b2o$786b2o12$773b2o12b2o$773b2o11bo2bo$787b2o4bo$792bobo$
792bobo$793bo8$774b2o$773bo2bo$774b2o4bo$779bobo$779bobo$780bo9$755b2o
$755b2o12$756b2o$755bo2bo$756b2o4bo$761bobo$761bobo$762bo4$742b2o$742b
2o12$743b2o$742bo2bo$743b2o4bo$727b2o19bobo$727b2o19bobo$749bo11$715b
2o11b2o$715b2o10bo2bo$728b2o4bo$733bobo$733bobo$734bo8$716b2o$715bo2bo
$701b2o13b2o4bo$701b2o18bobo$721bobo$722bo10$702b2o$701bo2bo$690b2o10b
2o4bo$690b2o15bobo$707bobo$708bo10$691b2o$690bo2bo$691b2o4bo$696bobo$
696bobo$673b2o22bo$673b2o12$674b2o$673bo2bo$674b2o4bo$659b2o18bobo$
659b2o18bobo$680bo11$660b2o$659bo2bo$660b2o4bo$665bobo$643b2o20bobo$
643b2o21bo10$632b2o$632b2o$644b2o$643bo2bo$644b2o4bo$649bobo$649bobo$
650bo6$633b2o$621b2o9bo2bo$621b2o10b2o4bo$638bobo$638bobo$639bo9$622b
2o$621bo2bo$622b2o4bo$627bobo$605b2o20bobo$605b2o21bo12$606b2o$605bo2b
o$606b2o4bo$590b2o19bobo$590b2o19bobo$612bo11$591b2o$590bo2bo$591b2o4b
o$596bobo$596bobo$573b2o22bo$573b2o12$574b2o$573bo2bo$574b2o4bo$558b2o
19bobo$558b2o19bobo$580bo11$559b2o$545b2o11bo2bo$545b2o12b2o4bo$564bob
o$564bobo$565bo9$546b2o$545bo2bo$546b2o4bo$531b2o18bobo$531b2o18bobo$
552bo11$532b2o$531bo2bo$532b2o4bo$537bobo$515b2o20bobo$515b2o21bo12$
516b2o$515bo2bo$501b2o13b2o4bo$501b2o18bobo$521bobo$522bo10$502b2o$
501bo2bo$502b2o4bo$507bobo$507bobo$484b2o22bo$484b2o12$485b2o$471b2o
11bo2bo$471b2o12b2o4bo$490bobo$490bobo$491bo9$461b2o9b2o$461b2o8bo2bo$
472b2o4bo$477bobo$477bobo$478bo6$450b2o$450b2o$462b2o$461bo2bo$462b2o
4bo$467bobo$467bobo$468bo6$451b2o$450bo2bo$451b2o4bo$436b2o18bobo$436b
2o18bobo$457bo9$424b2o$424b2o$437b2o$436bo2bo$437b2o4bo$442bobo$442bob
o$443bo6$425b2o$424bo2bo$425b2o4bo$430bobo$412b2o16bobo$412b2o17bo12$
413b2o$399b2o11bo2bo$399b2o12b2o4bo$418bobo$418bobo$419bo9$400b2o$384b
2o13bo2bo$384b2o14b2o4bo$405bobo$405bobo$406bo9$385b2o$384bo2bo$385b2o
4bo$369b2o19bobo$369b2o19bobo$391bo11$370b2o$369bo2bo$355b2o13b2o4bo$
355b2o18bobo$375bobo$376bo9$344b2o$344b2o10b2o$355bo2bo$356b2o4bo$361b
obo$361bobo$362bo7$345b2o$344bo2bo$345b2o4bo$350bobo$328b2o20bobo$328b
2o21bo12$317b2o10b2o$317b2o9bo2bo$329b2o4bo$334bobo$334bobo$335bo8$
318b2o$317bo2bo$318b2o4bo$323bobo$323bobo$324bo4$306b2o$306b2o9$289b2o
$289b2o2$307b2o$306bo2bo$307b2o4bo$312bobo$312bobo$313bo5$290b2o$289bo
2bo$290b2o4bo$295bobo$295bobo$296bo6$272b2o$272b2o12$273b2o$272bo2bo$
273b2o4bo$278bobo$278bobo$255b2o22bo$255b2o12$244b2o10b2o$244b2o9bo2bo
$256b2o4bo$261bobo$261bobo$262bo8$245b2o$244bo2bo$245b2o4bo$228b2o20bo
bo$228b2o20bobo$251bo9$218b2o$218b2o$229b2o$228bo2bo$229b2o4bo$234bobo
$234bobo$235bo6$219b2o$218bo2bo$219b2o4bo$224bobo$224bobo$225bo5$201b
2o$201b2o10$191b2o$191b2o$202b2o$201bo2bo$202b2o4bo$207bobo$207bobo$
208bo6$192b2o$191bo2bo$192b2o4bo$197bobo$197bobo$198bo5$175b2o$175b2o
12$176b2o$175bo2bo$176b2o4bo$181bobo$159b2o20bobo$159b2o21bo12$160b2o$
159bo2bo$160b2o4bo$165bobo$165bobo$144b2o20bo$144b2o12$145b2o$144bo2bo
$145b2o4bo$150bobo$150bobo$151bo6$128b2o$128b2o11$116b2o$116b2o11b2o$
128bo2bo$129b2o4bo$134bobo$134bobo$135bo7$117b2o$116bo2bo$117b2o4bo$
122bobo$122bobo$123bo14$109b2o$109b2o9$99b2o$99b2o2$110b2o$109bo2bo$
110b2o4bo$115bobo$115bobo$116bo5$100b2o$99bo2bo$100b2o4bo$105bobo$105b
obo$106bo9$90b2o$90b2o12$91b2o$90bo2bo$91b2o4bo$96bobo$96bobo$97bo108$
2o$2o!""",0,-1002)
optimized_offsets = []
evolved_delta = 0 # this will increase as we fast-forward the target pattern while always
# leaving the previous glider in place, about to strike --
# can't advance to stability, because then we wouldn't know about temporary sparks
# that extend salvo-source-wards, that might make the optimization unworkable
for item in zip(lanes, parities):
lane, parity = item
lane *= reverse_salvo
# we always know that the optimal glider position is somewhere between lowdelta and highdelta
# -- and when lowdelta and highdelta are the same value, we're done
# An assumption here is that the target object won't travel farther from its initial position,
# away from the slow-salvo source, than the distance between MIN_DELTA and INITIAL_DELTA.
# Increase INITIAL_DELTA if it seems possible that the target region will travel farther than this.
highdelta, lowdelta = INITIAL_DELTA, MIN_DELTA*2 - 1 - INITIAL_DELTA
# whatever happens when the glider is delayed by {delta} cells diagonally ...
# is what we want to be sure continues to happen in exactly the same way when we reduce the offset.
# So we'll start by defining the desired outcome to be whatever happens at the high end of the range.
#
# Let's say that the lowdelta variable will always contain the highest value that's known to not work
ticks = highdelta * 4 + LONG_ENOUGH
gliderpat = g.transform(EOlist[parity],(lane+1)//2+highdelta, highdelta)
expectedoutcome = g.evolve(g.join(targetpat, gliderpat), ticks)
while highdelta != lowdelta + 1:
newdelta = (lowdelta + 1 + highdelta) // 2 # bias toward the high side, since newdelta should never equal lowdelta
gliderpat = g.transform(EOlist[parity],(lane+1)//2+newdelta, newdelta)
outcome = g.evolve(g.join(targetpat, gliderpat), ticks)
if str(outcome)==str(expectedoutcome):
# the tested value is the new high value; rinse and repeat
# g.new("Still good")
# g.putcells(g.join(targetpat, gliderpat))
# g.fit()
# g.update()
# g.note("Still good at " + str(newdelta))
highdelta = newdelta
else:
# the tested value is the new low value; rinse and repeat
# g.new("No good")
# g.putcells(g.join(targetpat,gliderpat))
# g.fit()
# g.update()
# g.note("No good at " + str(newdelta))
lowdelta = newdelta
# it's possible that the binary search will find a value that's lower than
# the minimum optimization that we're allowing, 5 rows below the previous glider
# Strange things can happen when a slow glider arrives before its predecessor,
# so to keep things simple let's just set the minimum to 5.
if optimized_offsets!=[]:
if highdelta + evolved_delta - optimized_offsets[-1] < 5:
evolved_delta = optimized_offsets[-1] + 5 - highdelta
# At this point, lowdelta will contain the highest non-working glider location (that we're allowing),
# and highdelta will contain the lowest working glider location --
# with some possible exceptions: for example, an unusual spark from a previously colliding glider
# _could_ mean that some later glider locations (that we didn't happen to check) are unworkable.
# For these optimization purposes, this doesn't matter --
# we're only guaranteeing that the salvo is a slow salvo if we add 256 to each glider position.
optimized_offsets.append(highdelta+evolved_delta)
# We'll need a separate binary (?) search to determine how far we can advance the new targetpat+gliderpat pattern
# to produce a new targetpat and new expected outcome. It should be roughly the last tick before the
# gliderpat glider interacts with the previous targetpat -- but it can be a few ticks before that,
# if that makes it faster to check for the collision.
# To make the test faster, we can simply advance the combined target + glider pattern four ticks at a time,
# checking at each step whether the last cell in the cell list has a y value that has decreased by one.
# If no spark or explosion is moving slow-salvo-sourcewards yet, and the glider has not passed any
# stationary ash objects, then it's safe to advance that far. As soon as that's not true, stop.
testtargetpat = g.evolve(g.join(targetpat, g.transform(EOlist[parity],(lane+1)//2+highdelta, highdelta)), 4)
time_added = 0
southmost_y_value = testtargetpat[-1] # this is safe because we're working with two-state lists, no added zeroes at end of cell list
target_y_value = southmost_y_value
while target_y_value == southmost_y_value:
time_added += 4
newtargetpat = testtargetpat
testtargetpat = g.evolve(newtargetpat,4)
target_y_value -= 1
southmost_y_value = testtargetpat[-1]
g.new("Now testing time_added = " + str(time_added+4))
g.putcells(testtargetpat)
g.fit()
g.update()
# g.note("Southmost Y value = " + str(lowest_y_value))
# now newtargetpat contains the most advanced "safe" phase of the target pattern plus the latest glider,
# and time_added contains the number of ticks that the combined pattern was advanced
evolved_delta += time_added//4
targetpat = newtargetpat
# g.note("optimized offsets = " + str(optimized_offsets))
g.show(str(len(optimized_offsets)))
if len(optimized_offsets)>255:
break
g.show("Done.")
g.setclipstr(str(optimized_offsets))
This correctly finds the optimized locations I'm looking for, as evidenced by the fact that all the Corderships are generated in the right places. However, it doesn't give me quite the right list of deltas -- when I try "reconstituting" them with another script, the salvo works for a while, then succumbs to some kind of subtle timing failure.
The next task is to troubleshoot and find out why. If anyone is following along with this thread, let me know if any questions are coming up that I'm not answering. I'm including some comments in the code, but am not really sure if they're useful to my audience (because I'm not sure I have an audience.)