Secure Match Demonstration

We have developed an approach for secure evaluation of encrypted Boolean functions on encrypted bits. Building upon Barrington's work to transform circuits to group programs and the Feige-Kilian-Naor cryptographic protocol, our novel Fixed Structure Group Program construction for secure evaluation eliminates the need for an expensive Universal Circuit to hide the function. A third party weaves together and multiplies two coordinated streams of random sequences of elements from an unsolvable group; the Boolean decision is recovered while preserving the confidentiality of the decision function and the input bits. Our approach can handle expressions with NC1 complexity, which is the class of Acyclic Boolean Circuits with polynomial width and logarithmic depth in the size of the input. The approach is described in the following paper:

We illustrate the concept through an implementation in Scheme. Other prototypes written in jScheme and Java ran faster, supported larger circuit instances, and included simple expression parsers. The implementation presented here, however, is delivered over the web and runs within a Javascript-enabled browser using BiwaScheme, a Scheme interpreter written in Javascript. We extend BiwaScheme with one procedure (prngmore) for pseudo-random number generation based on Stanford Javascript Crypto Library, which is set up to collect entropy from mouse movements.


Loading ...
Move mouse to collect randomness


   Samples
  • ;; Specify decision in Acyclic Boolean circuit form '(NG (multi-and (multi-or 0 1 2) (AG 3 4) (NG 5)))
  • ;; Barrington transform: NOT => S5 group program (SPS..PS form) (ckt2gp '(NG 0)
  • ;; Barrington transform: AND => S5 group program (ckt2gp '(AG 0 1)
  • ;; Input bits (number 1729) => boolean list, pad to length 16 (i2bools 16 1729)
  • ;; Generate a dozen random bytes (prngmore 12)
  • ;; Run an end-to-end test, 2-bit NAND on all inputs 0 ... 3 (let* ((n 2) ; number of publisher bits (l 16) ; number of subscriber group program elements (rg (initrng 0)) ; seed random generator (nop) (r (next-randseq rg (* 4 n l))) ; draw random sequence for blinding (g (ckt2gp '(NG (AG 0 1))))) ; subscriber group program (display "Expecting #t#t#t#f, got: ") (for-each (lambda (x) (display (match ; secure match by third party (pubblind r n l (i2bools n x)) ; bits => GP => Feige-Kilian-Naor blinding (subblind r n l g)))) ; ckt => GP => Feige-Kilian-Naor blinding (iota 0 4 1)) (newline) 'DONE)

Secure Match Program Listing

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Secure evaluation of encrypted Boolean functions on encrypted bits ; Author: Rajesh Krishnan ; This is free and unencumbered software released into the public domain under the Unlicense ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Pre-computed tables for S5, computation logic provided later (define s5invtbl #(0 1 2 4 3 5 6 7 12 18 13 19 8 10 14 20 16 22 9 11 15 21 17 23 24 25 26 28 27 29 48 49 72 96 73 97 50 52 74 98 76 100 51 53 75 99 77 101 30 31 36 42 37 43 54 55 78 102 79 103 60 66 84 108 90 114 61 67 85 109 91 115 32 34 38 44 40 46 56 58 80 104 82 106 62 68 86 110 92 116 64 70 88 112 94 118 33 35 39 45 41 47 57 59 81 105 83 107 63 69 87 111 93 117 65 71 89 113 95 119)) (define s5multbl #( #(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119) #(1 0 4 5 2 3 7 6 10 11 8 9 18 19 20 21 22 23 12 13 14 15 16 17 25 24 28 29 26 27 31 30 34 35 32 33 42 43 44 45 46 47 36 37 38 39 40 41 49 48 52 53 50 51 55 54 58 59 56 57 66 67 68 69 70 71 60 61 62 63 64 65 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95) #(2 3 0 1 5 4 12 13 14 15 16 17 6 7 8 9 10 11 19 18 22 23 20 21 26 27 24 25 29 28 36 37 38 39 40 41 30 31 32 33 34 35 43 42 46 47 44 45 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 97 96 100 101 98 99 103 102 106 107 104 105 114 115 116 117 118 119 108 109 110 111 112 113) #(3 2 5 4 0 1 13 12 16 17 14 15 19 18 22 23 20 21 6 7 8 9 10 11 27 26 29 28 24 25 37 36 40 41 38 39 43 42 46 47 44 45 30 31 32 33 34 35 73 72 76 77 74 75 79 78 82 83 80 81 90 91 92 93 94 95 84 85 86 87 88 89 97 96 100 101 98 99 103 102 106 107 104 105 114 115 116 117 118 119 108 109 110 111 112 113 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71) #(4 5 1 0 3 2 18 19 20 21 22 23 7 6 10 11 8 9 13 12 16 17 14 15 28 29 25 24 27 26 42 43 44 45 46 47 31 30 34 35 32 33 37 36 40 41 38 39 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 49 48 52 53 50 51 55 54 58 59 56 57 66 67 68 69 70 71 60 61 62 63 64 65 73 72 76 77 74 75 79 78 82 83 80 81 90 91 92 93 94 95 84 85 86 87 88 89) #(5 4 3 2 1 0 19 18 22 23 20 21 13 12 16 17 14 15 7 6 10 11 8 9 29 28 27 26 25 24 43 42 46 47 44 45 37 36 40 41 38 39 31 30 34 35 32 33 97 96 100 101 98 99 103 102 106 107 104 105 114 115 116 117 118 119 108 109 110 111 112 113 73 72 76 77 74 75 79 78 82 83 80 81 90 91 92 93 94 95 84 85 86 87 88 89 49 48 52 53 50 51 55 54 58 59 56 57 66 67 68 69 70 71 60 61 62 63 64 65) #(6 7 8 9 10 11 0 1 2 3 4 5 14 15 12 13 17 16 20 21 18 19 23 22 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 74 75 72 73 77 76 84 85 86 87 88 89 78 79 80 81 82 83 91 90 94 95 92 93 98 99 96 97 101 100 108 109 110 111 112 113 102 103 104 105 106 107 115 114 118 119 116 117) #(7 6 10 11 8 9 1 0 4 5 2 3 20 21 18 19 23 22 14 15 12 13 17 16 49 48 52 53 50 51 55 54 58 59 56 57 66 67 68 69 70 71 60 61 62 63 64 65 25 24 28 29 26 27 31 30 34 35 32 33 42 43 44 45 46 47 36 37 38 39 40 41 98 99 96 97 101 100 108 109 110 111 112 113 102 103 104 105 106 107 115 114 118 119 116 117 74 75 72 73 77 76 84 85 86 87 88 89 78 79 80 81 82 83 91 90 94 95 92 93) #(8 9 6 7 11 10 14 15 12 13 17 16 0 1 2 3 4 5 21 20 23 22 18 19 50 51 48 49 53 52 60 61 62 63 64 65 54 55 56 57 58 59 67 66 70 71 68 69 74 75 72 73 77 76 84 85 86 87 88 89 78 79 80 81 82 83 91 90 94 95 92 93 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 99 98 101 100 96 97 109 108 112 113 110 111 115 114 118 119 116 117 102 103 104 105 106 107) #(9 8 11 10 6 7 15 14 17 16 12 13 21 20 23 22 18 19 0 1 2 3 4 5 51 50 53 52 48 49 61 60 64 65 62 63 67 66 70 71 68 69 54 55 56 57 58 59 75 74 77 76 72 73 85 84 88 89 86 87 91 90 94 95 92 93 78 79 80 81 82 83 99 98 101 100 96 97 109 108 112 113 110 111 115 114 118 119 116 117 102 103 104 105 106 107 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47) #(10 11 7 6 9 8 20 21 18 19 23 22 1 0 4 5 2 3 15 14 17 16 12 13 52 53 49 48 51 50 66 67 68 69 70 71 55 54 58 59 56 57 61 60 64 65 62 63 98 99 96 97 101 100 108 109 110 111 112 113 102 103 104 105 106 107 115 114 118 119 116 117 25 24 28 29 26 27 31 30 34 35 32 33 42 43 44 45 46 47 36 37 38 39 40 41 75 74 77 76 72 73 85 84 88 89 86 87 91 90 94 95 92 93 78 79 80 81 82 83) #(11 10 9 8 7 6 21 20 23 22 18 19 15 14 17 16 12 13 1 0 4 5 2 3 53 52 51 50 49 48 67 66 70 71 68 69 61 60 64 65 62 63 55 54 58 59 56 57 99 98 101 100 96 97 109 108 112 113 110 111 115 114 118 119 116 117 102 103 104 105 106 107 75 74 77 76 72 73 85 84 88 89 86 87 91 90 94 95 92 93 78 79 80 81 82 83 25 24 28 29 26 27 31 30 34 35 32 33 42 43 44 45 46 47 36 37 38 39 40 41) #(12 13 14 15 16 17 2 3 0 1 5 4 8 9 6 7 11 10 22 23 19 18 21 20 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 26 27 24 25 29 28 36 37 38 39 40 41 30 31 32 33 34 35 43 42 46 47 44 45 50 51 48 49 53 52 60 61 62 63 64 65 54 55 56 57 58 59 67 66 70 71 68 69 100 101 97 96 99 98 114 115 116 117 118 119 103 102 106 107 104 105 109 108 112 113 110 111) #(13 12 16 17 14 15 3 2 5 4 0 1 22 23 19 18 21 20 8 9 6 7 11 10 73 72 76 77 74 75 79 78 82 83 80 81 90 91 92 93 94 95 84 85 86 87 88 89 27 26 29 28 24 25 37 36 40 41 38 39 43 42 46 47 44 45 30 31 32 33 34 35 100 101 97 96 99 98 114 115 116 117 118 119 103 102 106 107 104 105 109 108 112 113 110 111 50 51 48 49 53 52 60 61 62 63 64 65 54 55 56 57 58 59 67 66 70 71 68 69) #(14 15 12 13 17 16 8 9 6 7 11 10 2 3 0 1 5 4 23 22 21 20 19 18 74 75 72 73 77 76 84 85 86 87 88 89 78 79 80 81 82 83 91 90 94 95 92 93 50 51 48 49 53 52 60 61 62 63 64 65 54 55 56 57 58 59 67 66 70 71 68 69 26 27 24 25 29 28 36 37 38 39 40 41 30 31 32 33 34 35 43 42 46 47 44 45 101 100 99 98 97 96 115 114 118 119 116 117 109 108 112 113 110 111 103 102 106 107 104 105) #(15 14 17 16 12 13 9 8 11 10 6 7 23 22 21 20 19 18 2 3 0 1 5 4 75 74 77 76 72 73 85 84 88 89 86 87 91 90 94 95 92 93 78 79 80 81 82 83 51 50 53 52 48 49 61 60 64 65 62 63 67 66 70 71 68 69 54 55 56 57 58 59 101 100 99 98 97 96 115 114 118 119 116 117 109 108 112 113 110 111 103 102 106 107 104 105 26 27 24 25 29 28 36 37 38 39 40 41 30 31 32 33 34 35 43 42 46 47 44 45) #(16 17 13 12 15 14 22 23 19 18 21 20 3 2 5 4 0 1 9 8 11 10 6 7 76 77 73 72 75 74 90 91 92 93 94 95 79 78 82 83 80 81 85 84 88 89 86 87 100 101 97 96 99 98 114 115 116 117 118 119 103 102 106 107 104 105 109 108 112 113 110 111 27 26 29 28 24 25 37 36 40 41 38 39 43 42 46 47 44 45 30 31 32 33 34 35 51 50 53 52 48 49 61 60 64 65 62 63 67 66 70 71 68 69 54 55 56 57 58 59) #(17 16 15 14 13 12 23 22 21 20 19 18 9 8 11 10 6 7 3 2 5 4 0 1 77 76 75 74 73 72 91 90 94 95 92 93 85 84 88 89 86 87 79 78 82 83 80 81 101 100 99 98 97 96 115 114 118 119 116 117 109 108 112 113 110 111 103 102 106 107 104 105 51 50 53 52 48 49 61 60 64 65 62 63 67 66 70 71 68 69 54 55 56 57 58 59 27 26 29 28 24 25 37 36 40 41 38 39 43 42 46 47 44 45 30 31 32 33 34 35) #(18 19 20 21 22 23 4 5 1 0 3 2 10 11 7 6 9 8 16 17 13 12 15 14 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 28 29 25 24 27 26 42 43 44 45 46 47 31 30 34 35 32 33 37 36 40 41 38 39 52 53 49 48 51 50 66 67 68 69 70 71 55 54 58 59 56 57 61 60 64 65 62 63 76 77 73 72 75 74 90 91 92 93 94 95 79 78 82 83 80 81 85 84 88 89 86 87) #(19 18 22 23 20 21 5 4 3 2 1 0 16 17 13 12 15 14 10 11 7 6 9 8 97 96 100 101 98 99 103 102 106 107 104 105 114 115 116 117 118 119 108 109 110 111 112 113 29 28 27 26 25 24 43 42 46 47 44 45 37 36 40 41 38 39 31 30 34 35 32 33 76 77 73 72 75 74 90 91 92 93 94 95 79 78 82 83 80 81 85 84 88 89 86 87 52 53 49 48 51 50 66 67 68 69 70 71 55 54 58 59 56 57 61 60 64 65 62 63) #(20 21 18 19 23 22 10 11 7 6 9 8 4 5 1 0 3 2 17 16 15 14 13 12 98 99 96 97 101 100 108 109 110 111 112 113 102 103 104 105 106 107 115 114 118 119 116 117 52 53 49 48 51 50 66 67 68 69 70 71 55 54 58 59 56 57 61 60 64 65 62 63 28 29 25 24 27 26 42 43 44 45 46 47 31 30 34 35 32 33 37 36 40 41 38 39 77 76 75 74 73 72 91 90 94 95 92 93 85 84 88 89 86 87 79 78 82 83 80 81) #(21 20 23 22 18 19 11 10 9 8 7 6 17 16 15 14 13 12 4 5 1 0 3 2 99 98 101 100 96 97 109 108 112 113 110 111 115 114 118 119 116 117 102 103 104 105 106 107 53 52 51 50 49 48 67 66 70 71 68 69 61 60 64 65 62 63 55 54 58 59 56 57 77 76 75 74 73 72 91 90 94 95 92 93 85 84 88 89 86 87 79 78 82 83 80 81 28 29 25 24 27 26 42 43 44 45 46 47 31 30 34 35 32 33 37 36 40 41 38 39) #(22 23 19 18 21 20 16 17 13 12 15 14 5 4 3 2 1 0 11 10 9 8 7 6 100 101 97 96 99 98 114 115 116 117 118 119 103 102 106 107 104 105 109 108 112 113 110 111 76 77 73 72 75 74 90 91 92 93 94 95 79 78 82 83 80 81 85 84 88 89 86 87 29 28 27 26 25 24 43 42 46 47 44 45 37 36 40 41 38 39 31 30 34 35 32 33 53 52 51 50 49 48 67 66 70 71 68 69 61 60 64 65 62 63 55 54 58 59 56 57) #(23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 101 100 99 98 97 96 115 114 118 119 116 117 109 108 112 113 110 111 103 102 106 107 104 105 77 76 75 74 73 72 91 90 94 95 92 93 85 84 88 89 86 87 79 78 82 83 80 81 53 52 51 50 49 48 67 66 70 71 68 69 61 60 64 65 62 63 55 54 58 59 56 57 29 28 27 26 25 24 43 42 46 47 44 45 37 36 40 41 38 39 31 30 34 35 32 33) #(24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 54 55 56 57 58 59 48 49 50 51 52 53 62 63 60 61 65 64 68 69 66 67 71 70 78 79 80 81 82 83 72 73 74 75 76 77 86 87 84 85 89 88 92 93 90 91 95 94 102 103 104 105 106 107 96 97 98 99 100 101 110 111 108 109 113 112 116 117 114 115 119 118) #(25 24 28 29 26 27 31 30 34 35 32 33 42 43 44 45 46 47 36 37 38 39 40 41 1 0 4 5 2 3 7 6 10 11 8 9 18 19 20 21 22 23 12 13 14 15 16 17 55 54 58 59 56 57 49 48 52 53 50 51 68 69 66 67 71 70 62 63 60 61 65 64 102 103 104 105 106 107 96 97 98 99 100 101 110 111 108 109 113 112 116 117 114 115 119 118 78 79 80 81 82 83 72 73 74 75 76 77 86 87 84 85 89 88 92 93 90 91 95 94) #(26 27 24 25 29 28 36 37 38 39 40 41 30 31 32 33 34 35 43 42 46 47 44 45 2 3 0 1 5 4 12 13 14 15 16 17 6 7 8 9 10 11 19 18 22 23 20 21 78 79 80 81 82 83 72 73 74 75 76 77 86 87 84 85 89 88 92 93 90 91 95 94 54 55 56 57 58 59 48 49 50 51 52 53 62 63 60 61 65 64 68 69 66 67 71 70 103 102 106 107 104 105 97 96 100 101 98 99 116 117 114 115 119 118 110 111 108 109 113 112) #(27 26 29 28 24 25 37 36 40 41 38 39 43 42 46 47 44 45 30 31 32 33 34 35 3 2 5 4 0 1 13 12 16 17 14 15 19 18 22 23 20 21 6 7 8 9 10 11 79 78 82 83 80 81 73 72 76 77 74 75 92 93 90 91 95 94 86 87 84 85 89 88 103 102 106 107 104 105 97 96 100 101 98 99 116 117 114 115 119 118 110 111 108 109 113 112 54 55 56 57 58 59 48 49 50 51 52 53 62 63 60 61 65 64 68 69 66 67 71 70) #(28 29 25 24 27 26 42 43 44 45 46 47 31 30 34 35 32 33 37 36 40 41 38 39 4 5 1 0 3 2 18 19 20 21 22 23 7 6 10 11 8 9 13 12 16 17 14 15 102 103 104 105 106 107 96 97 98 99 100 101 110 111 108 109 113 112 116 117 114 115 119 118 55 54 58 59 56 57 49 48 52 53 50 51 68 69 66 67 71 70 62 63 60 61 65 64 79 78 82 83 80 81 73 72 76 77 74 75 92 93 90 91 95 94 86 87 84 85 89 88) #(29 28 27 26 25 24 43 42 46 47 44 45 37 36 40 41 38 39 31 30 34 35 32 33 5 4 3 2 1 0 19 18 22 23 20 21 13 12 16 17 14 15 7 6 10 11 8 9 103 102 106 107 104 105 97 96 100 101 98 99 116 117 114 115 119 118 110 111 108 109 113 112 79 78 82 83 80 81 73 72 76 77 74 75 92 93 90 91 95 94 86 87 84 85 89 88 55 54 58 59 56 57 49 48 52 53 50 51 68 69 66 67 71 70 62 63 60 61 65 64) #(30 31 32 33 34 35 24 25 26 27 28 29 38 39 36 37 41 40 44 45 42 43 47 46 54 55 56 57 58 59 48 49 50 51 52 53 62 63 60 61 65 64 68 69 66 67 71 70 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 80 81 78 79 83 82 86 87 84 85 89 88 72 73 74 75 76 77 93 92 95 94 90 91 104 105 102 103 107 106 110 111 108 109 113 112 96 97 98 99 100 101 117 116 119 118 114 115) #(31 30 34 35 32 33 25 24 28 29 26 27 44 45 42 43 47 46 38 39 36 37 41 40 55 54 58 59 56 57 49 48 52 53 50 51 68 69 66 67 71 70 62 63 60 61 65 64 1 0 4 5 2 3 7 6 10 11 8 9 18 19 20 21 22 23 12 13 14 15 16 17 104 105 102 103 107 106 110 111 108 109 113 112 96 97 98 99 100 101 117 116 119 118 114 115 80 81 78 79 83 82 86 87 84 85 89 88 72 73 74 75 76 77 93 92 95 94 90 91) #(32 33 30 31 35 34 38 39 36 37 41 40 24 25 26 27 28 29 45 44 47 46 42 43 56 57 54 55 59 58 62 63 60 61 65 64 48 49 50 51 52 53 69 68 71 70 66 67 80 81 78 79 83 82 86 87 84 85 89 88 72 73 74 75 76 77 93 92 95 94 90 91 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 105 104 107 106 102 103 111 110 113 112 108 109 117 116 119 118 114 115 96 97 98 99 100 101) #(33 32 35 34 30 31 39 38 41 40 36 37 45 44 47 46 42 43 24 25 26 27 28 29 57 56 59 58 54 55 63 62 65 64 60 61 69 68 71 70 66 67 48 49 50 51 52 53 81 80 83 82 78 79 87 86 89 88 84 85 93 92 95 94 90 91 72 73 74 75 76 77 105 104 107 106 102 103 111 110 113 112 108 109 117 116 119 118 114 115 96 97 98 99 100 101 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) #(34 35 31 30 33 32 44 45 42 43 47 46 25 24 28 29 26 27 39 38 41 40 36 37 58 59 55 54 57 56 68 69 66 67 71 70 49 48 52 53 50 51 63 62 65 64 60 61 104 105 102 103 107 106 110 111 108 109 113 112 96 97 98 99 100 101 117 116 119 118 114 115 1 0 4 5 2 3 7 6 10 11 8 9 18 19 20 21 22 23 12 13 14 15 16 17 81 80 83 82 78 79 87 86 89 88 84 85 93 92 95 94 90 91 72 73 74 75 76 77) #(35 34 33 32 31 30 45 44 47 46 42 43 39 38 41 40 36 37 25 24 28 29 26 27 59 58 57 56 55 54 69 68 71 70 66 67 63 62 65 64 60 61 49 48 52 53 50 51 105 104 107 106 102 103 111 110 113 112 108 109 117 116 119 118 114 115 96 97 98 99 100 101 81 80 83 82 78 79 87 86 89 88 84 85 93 92 95 94 90 91 72 73 74 75 76 77 1 0 4 5 2 3 7 6 10 11 8 9 18 19 20 21 22 23 12 13 14 15 16 17) #(36 37 38 39 40 41 26 27 24 25 29 28 32 33 30 31 35 34 46 47 43 42 45 44 78 79 80 81 82 83 72 73 74 75 76 77 86 87 84 85 89 88 92 93 90 91 95 94 2 3 0 1 5 4 12 13 14 15 16 17 6 7 8 9 10 11 19 18 22 23 20 21 56 57 54 55 59 58 62 63 60 61 65 64 48 49 50 51 52 53 69 68 71 70 66 67 106 107 103 102 105 104 116 117 114 115 119 118 97 96 100 101 98 99 111 110 113 112 108 109) #(37 36 40 41 38 39 27 26 29 28 24 25 46 47 43 42 45 44 32 33 30 31 35 34 79 78 82 83 80 81 73 72 76 77 74 75 92 93 90 91 95 94 86 87 84 85 89 88 3 2 5 4 0 1 13 12 16 17 14 15 19 18 22 23 20 21 6 7 8 9 10 11 106 107 103 102 105 104 116 117 114 115 119 118 97 96 100 101 98 99 111 110 113 112 108 109 56 57 54 55 59 58 62 63 60 61 65 64 48 49 50 51 52 53 69 68 71 70 66 67) #(38 39 36 37 41 40 32 33 30 31 35 34 26 27 24 25 29 28 47 46 45 44 43 42 80 81 78 79 83 82 86 87 84 85 89 88 72 73 74 75 76 77 93 92 95 94 90 91 56 57 54 55 59 58 62 63 60 61 65 64 48 49 50 51 52 53 69 68 71 70 66 67 2 3 0 1 5 4 12 13 14 15 16 17 6 7 8 9 10 11 19 18 22 23 20 21 107 106 105 104 103 102 117 116 119 118 114 115 111 110 113 112 108 109 97 96 100 101 98 99) #(39 38 41 40 36 37 33 32 35 34 30 31 47 46 45 44 43 42 26 27 24 25 29 28 81 80 83 82 78 79 87 86 89 88 84 85 93 92 95 94 90 91 72 73 74 75 76 77 57 56 59 58 54 55 63 62 65 64 60 61 69 68 71 70 66 67 48 49 50 51 52 53 107 106 105 104 103 102 117 116 119 118 114 115 111 110 113 112 108 109 97 96 100 101 98 99 2 3 0 1 5 4 12 13 14 15 16 17 6 7 8 9 10 11 19 18 22 23 20 21) #(40 41 37 36 39 38 46 47 43 42 45 44 27 26 29 28 24 25 33 32 35 34 30 31 82 83 79 78 81 80 92 93 90 91 95 94 73 72 76 77 74 75 87 86 89 88 84 85 106 107 103 102 105 104 116 117 114 115 119 118 97 96 100 101 98 99 111 110 113 112 108 109 3 2 5 4 0 1 13 12 16 17 14 15 19 18 22 23 20 21 6 7 8 9 10 11 57 56 59 58 54 55 63 62 65 64 60 61 69 68 71 70 66 67 48 49 50 51 52 53) #(41 40 39 38 37 36 47 46 45 44 43 42 33 32 35 34 30 31 27 26 29 28 24 25 83 82 81 80 79 78 93 92 95 94 90 91 87 86 89 88 84 85 73 72 76 77 74 75 107 106 105 104 103 102 117 116 119 118 114 115 111 110 113 112 108 109 97 96 100 101 98 99 57 56 59 58 54 55 63 62 65 64 60 61 69 68 71 70 66 67 48 49 50 51 52 53 3 2 5 4 0 1 13 12 16 17 14 15 19 18 22 23 20 21 6 7 8 9 10 11) #(42 43 44 45 46 47 28 29 25 24 27 26 34 35 31 30 33 32 40 41 37 36 39 38 102 103 104 105 106 107 96 97 98 99 100 101 110 111 108 109 113 112 116 117 114 115 119 118 4 5 1 0 3 2 18 19 20 21 22 23 7 6 10 11 8 9 13 12 16 17 14 15 58 59 55 54 57 56 68 69 66 67 71 70 49 48 52 53 50 51 63 62 65 64 60 61 82 83 79 78 81 80 92 93 90 91 95 94 73 72 76 77 74 75 87 86 89 88 84 85) #(43 42 46 47 44 45 29 28 27 26 25 24 40 41 37 36 39 38 34 35 31 30 33 32 103 102 106 107 104 105 97 96 100 101 98 99 116 117 114 115 119 118 110 111 108 109 113 112 5 4 3 2 1 0 19 18 22 23 20 21 13 12 16 17 14 15 7 6 10 11 8 9 82 83 79 78 81 80 92 93 90 91 95 94 73 72 76 77 74 75 87 86 89 88 84 85 58 59 55 54 57 56 68 69 66 67 71 70 49 48 52 53 50 51 63 62 65 64 60 61) #(44 45 42 43 47 46 34 35 31 30 33 32 28 29 25 24 27 26 41 40 39 38 37 36 104 105 102 103 107 106 110 111 108 109 113 112 96 97 98 99 100 101 117 116 119 118 114 115 58 59 55 54 57 56 68 69 66 67 71 70 49 48 52 53 50 51 63 62 65 64 60 61 4 5 1 0 3 2 18 19 20 21 22 23 7 6 10 11 8 9 13 12 16 17 14 15 83 82 81 80 79 78 93 92 95 94 90 91 87 86 89 88 84 85 73 72 76 77 74 75) #(45 44 47 46 42 43 35 34 33 32 31 30 41 40 39 38 37 36 28 29 25 24 27 26 105 104 107 106 102 103 111 110 113 112 108 109 117 116 119 118 114 115 96 97 98 99 100 101 59 58 57 56 55 54 69 68 71 70 66 67 63 62 65 64 60 61 49 48 52 53 50 51 83 82 81 80 79 78 93 92 95 94 90 91 87 86 89 88 84 85 73 72 76 77 74 75 4 5 1 0 3 2 18 19 20 21 22 23 7 6 10 11 8 9 13 12 16 17 14 15) #(46 47 43 42 45 44 40 41 37 36 39 38 29 28 27 26 25 24 35 34 33 32 31 30 106 107 103 102 105 104 116 117 114 115 119 118 97 96 100 101 98 99 111 110 113 112 108 109 82 83 79 78 81 80 92 93 90 91 95 94 73 72 76 77 74 75 87 86 89 88 84 85 5 4 3 2 1 0 19 18 22 23 20 21 13 12 16 17 14 15 7 6 10 11 8 9 59 58 57 56 55 54 69 68 71 70 66 67 63 62 65 64 60 61 49 48 52 53 50 51) #(47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 107 106 105 104 103 102 117 116 119 118 114 115 111 110 113 112 108 109 97 96 100 101 98 99 83 82 81 80 79 78 93 92 95 94 90 91 87 86 89 88 84 85 73 72 76 77 74 75 59 58 57 56 55 54 69 68 71 70 66 67 63 62 65 64 60 61 49 48 52 53 50 51 5 4 3 2 1 0 19 18 22 23 20 21 13 12 16 17 14 15 7 6 10 11 8 9) #(48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 6 7 8 9 10 11 0 1 2 3 4 5 14 15 12 13 17 16 20 21 18 19 23 22 30 31 32 33 34 35 24 25 26 27 28 29 38 39 36 37 41 40 44 45 42 43 47 46 84 85 86 87 88 89 74 75 72 73 77 76 80 81 78 79 83 82 94 95 91 90 93 92 108 109 110 111 112 113 98 99 96 97 101 100 104 105 102 103 107 106 118 119 115 114 117 116) #(49 48 52 53 50 51 55 54 58 59 56 57 66 67 68 69 70 71 60 61 62 63 64 65 7 6 10 11 8 9 1 0 4 5 2 3 20 21 18 19 23 22 14 15 12 13 17 16 31 30 34 35 32 33 25 24 28 29 26 27 44 45 42 43 47 46 38 39 36 37 41 40 108 109 110 111 112 113 98 99 96 97 101 100 104 105 102 103 107 106 118 119 115 114 117 116 84 85 86 87 88 89 74 75 72 73 77 76 80 81 78 79 83 82 94 95 91 90 93 92) #(50 51 48 49 53 52 60 61 62 63 64 65 54 55 56 57 58 59 67 66 70 71 68 69 8 9 6 7 11 10 14 15 12 13 17 16 0 1 2 3 4 5 21 20 23 22 18 19 84 85 86 87 88 89 74 75 72 73 77 76 80 81 78 79 83 82 94 95 91 90 93 92 30 31 32 33 34 35 24 25 26 27 28 29 38 39 36 37 41 40 44 45 42 43 47 46 109 108 112 113 110 111 99 98 101 100 96 97 118 119 115 114 117 116 104 105 102 103 107 106) #(51 50 53 52 48 49 61 60 64 65 62 63 67 66 70 71 68 69 54 55 56 57 58 59 9 8 11 10 6 7 15 14 17 16 12 13 21 20 23 22 18 19 0 1 2 3 4 5 85 84 88 89 86 87 75 74 77 76 72 73 94 95 91 90 93 92 80 81 78 79 83 82 109 108 112 113 110 111 99 98 101 100 96 97 118 119 115 114 117 116 104 105 102 103 107 106 30 31 32 33 34 35 24 25 26 27 28 29 38 39 36 37 41 40 44 45 42 43 47 46) #(52 53 49 48 51 50 66 67 68 69 70 71 55 54 58 59 56 57 61 60 64 65 62 63 10 11 7 6 9 8 20 21 18 19 23 22 1 0 4 5 2 3 15 14 17 16 12 13 108 109 110 111 112 113 98 99 96 97 101 100 104 105 102 103 107 106 118 119 115 114 117 116 31 30 34 35 32 33 25 24 28 29 26 27 44 45 42 43 47 46 38 39 36 37 41 40 85 84 88 89 86 87 75 74 77 76 72 73 94 95 91 90 93 92 80 81 78 79 83 82) #(53 52 51 50 49 48 67 66 70 71 68 69 61 60 64 65 62 63 55 54 58 59 56 57 11 10 9 8 7 6 21 20 23 22 18 19 15 14 17 16 12 13 1 0 4 5 2 3 109 108 112 113 110 111 99 98 101 100 96 97 118 119 115 114 117 116 104 105 102 103 107 106 85 84 88 89 86 87 75 74 77 76 72 73 94 95 91 90 93 92 80 81 78 79 83 82 31 30 34 35 32 33 25 24 28 29 26 27 44 45 42 43 47 46 38 39 36 37 41 40) #(54 55 56 57 58 59 48 49 50 51 52 53 62 63 60 61 65 64 68 69 66 67 71 70 30 31 32 33 34 35 24 25 26 27 28 29 38 39 36 37 41 40 44 45 42 43 47 46 6 7 8 9 10 11 0 1 2 3 4 5 14 15 12 13 17 16 20 21 18 19 23 22 86 87 84 85 89 88 80 81 78 79 83 82 74 75 72 73 77 76 95 94 93 92 91 90 110 111 108 109 113 112 104 105 102 103 107 106 98 99 96 97 101 100 119 118 117 116 115 114) #(55 54 58 59 56 57 49 48 52 53 50 51 68 69 66 67 71 70 62 63 60 61 65 64 31 30 34 35 32 33 25 24 28 29 26 27 44 45 42 43 47 46 38 39 36 37 41 40 7 6 10 11 8 9 1 0 4 5 2 3 20 21 18 19 23 22 14 15 12 13 17 16 110 111 108 109 113 112 104 105 102 103 107 106 98 99 96 97 101 100 119 118 117 116 115 114 86 87 84 85 89 88 80 81 78 79 83 82 74 75 72 73 77 76 95 94 93 92 91 90) #(56 57 54 55 59 58 62 63 60 61 65 64 48 49 50 51 52 53 69 68 71 70 66 67 32 33 30 31 35 34 38 39 36 37 41 40 24 25 26 27 28 29 45 44 47 46 42 43 86 87 84 85 89 88 80 81 78 79 83 82 74 75 72 73 77 76 95 94 93 92 91 90 6 7 8 9 10 11 0 1 2 3 4 5 14 15 12 13 17 16 20 21 18 19 23 22 111 110 113 112 108 109 105 104 107 106 102 103 119 118 117 116 115 114 98 99 96 97 101 100) #(57 56 59 58 54 55 63 62 65 64 60 61 69 68 71 70 66 67 48 49 50 51 52 53 33 32 35 34 30 31 39 38 41 40 36 37 45 44 47 46 42 43 24 25 26 27 28 29 87 86 89 88 84 85 81 80 83 82 78 79 95 94 93 92 91 90 74 75 72 73 77 76 111 110 113 112 108 109 105 104 107 106 102 103 119 118 117 116 115 114 98 99 96 97 101 100 6 7 8 9 10 11 0 1 2 3 4 5 14 15 12 13 17 16 20 21 18 19 23 22) #(58 59 55 54 57 56 68 69 66 67 71 70 49 48 52 53 50 51 63 62 65 64 60 61 34 35 31 30 33 32 44 45 42 43 47 46 25 24 28 29 26 27 39 38 41 40 36 37 110 111 108 109 113 112 104 105 102 103 107 106 98 99 96 97 101 100 119 118 117 116 115 114 7 6 10 11 8 9 1 0 4 5 2 3 20 21 18 19 23 22 14 15 12 13 17 16 87 86 89 88 84 85 81 80 83 82 78 79 95 94 93 92 91 90 74 75 72 73 77 76) #(59 58 57 56 55 54 69 68 71 70 66 67 63 62 65 64 60 61 49 48 52 53 50 51 35 34 33 32 31 30 45 44 47 46 42 43 39 38 41 40 36 37 25 24 28 29 26 27 111 110 113 112 108 109 105 104 107 106 102 103 119 118 117 116 115 114 98 99 96 97 101 100 87 86 89 88 84 85 81 80 83 82 78 79 95 94 93 92 91 90 74 75 72 73 77 76 7 6 10 11 8 9 1 0 4 5 2 3 20 21 18 19 23 22 14 15 12 13 17 16) #(60 61 62 63 64 65 50 51 48 49 53 52 56 57 54 55 59 58 70 71 67 66 69 68 84 85 86 87 88 89 74 75 72 73 77 76 80 81 78 79 83 82 94 95 91 90 93 92 8 9 6 7 11 10 14 15 12 13 17 16 0 1 2 3 4 5 21 20 23 22 18 19 32 33 30 31 35 34 38 39 36 37 41 40 24 25 26 27 28 29 45 44 47 46 42 43 112 113 109 108 111 110 118 119 115 114 117 116 99 98 101 100 96 97 105 104 107 106 102 103) #(61 60 64 65 62 63 51 50 53 52 48 49 70 71 67 66 69 68 56 57 54 55 59 58 85 84 88 89 86 87 75 74 77 76 72 73 94 95 91 90 93 92 80 81 78 79 83 82 9 8 11 10 6 7 15 14 17 16 12 13 21 20 23 22 18 19 0 1 2 3 4 5 112 113 109 108 111 110 118 119 115 114 117 116 99 98 101 100 96 97 105 104 107 106 102 103 32 33 30 31 35 34 38 39 36 37 41 40 24 25 26 27 28 29 45 44 47 46 42 43) #(62 63 60 61 65 64 56 57 54 55 59 58 50 51 48 49 53 52 71 70 69 68 67 66 86 87 84 85 89 88 80 81 78 79 83 82 74 75 72 73 77 76 95 94 93 92 91 90 32 33 30 31 35 34 38 39 36 37 41 40 24 25 26 27 28 29 45 44 47 46 42 43 8 9 6 7 11 10 14 15 12 13 17 16 0 1 2 3 4 5 21 20 23 22 18 19 113 112 111 110 109 108 119 118 117 116 115 114 105 104 107 106 102 103 99 98 101 100 96 97) #(63 62 65 64 60 61 57 56 59 58 54 55 71 70 69 68 67 66 50 51 48 49 53 52 87 86 89 88 84 85 81 80 83 82 78 79 95 94 93 92 91 90 74 75 72 73 77 76 33 32 35 34 30 31 39 38 41 40 36 37 45 44 47 46 42 43 24 25 26 27 28 29 113 112 111 110 109 108 119 118 117 116 115 114 105 104 107 106 102 103 99 98 101 100 96 97 8 9 6 7 11 10 14 15 12 13 17 16 0 1 2 3 4 5 21 20 23 22 18 19) #(64 65 61 60 63 62 70 71 67 66 69 68 51 50 53 52 48 49 57 56 59 58 54 55 88 89 85 84 87 86 94 95 91 90 93 92 75 74 77 76 72 73 81 80 83 82 78 79 112 113 109 108 111 110 118 119 115 114 117 116 99 98 101 100 96 97 105 104 107 106 102 103 9 8 11 10 6 7 15 14 17 16 12 13 21 20 23 22 18 19 0 1 2 3 4 5 33 32 35 34 30 31 39 38 41 40 36 37 45 44 47 46 42 43 24 25 26 27 28 29) #(65 64 63 62 61 60 71 70 69 68 67 66 57 56 59 58 54 55 51 50 53 52 48 49 89 88 87 86 85 84 95 94 93 92 91 90 81 80 83 82 78 79 75 74 77 76 72 73 113 112 111 110 109 108 119 118 117 116 115 114 105 104 107 106 102 103 99 98 101 100 96 97 33 32 35 34 30 31 39 38 41 40 36 37 45 44 47 46 42 43 24 25 26 27 28 29 9 8 11 10 6 7 15 14 17 16 12 13 21 20 23 22 18 19 0 1 2 3 4 5) #(66 67 68 69 70 71 52 53 49 48 51 50 58 59 55 54 57 56 64 65 61 60 63 62 108 109 110 111 112 113 98 99 96 97 101 100 104 105 102 103 107 106 118 119 115 114 117 116 10 11 7 6 9 8 20 21 18 19 23 22 1 0 4 5 2 3 15 14 17 16 12 13 34 35 31 30 33 32 44 45 42 43 47 46 25 24 28 29 26 27 39 38 41 40 36 37 88 89 85 84 87 86 94 95 91 90 93 92 75 74 77 76 72 73 81 80 83 82 78 79) #(67 66 70 71 68 69 53 52 51 50 49 48 64 65 61 60 63 62 58 59 55 54 57 56 109 108 112 113 110 111 99 98 101 100 96 97 118 119 115 114 117 116 104 105 102 103 107 106 11 10 9 8 7 6 21 20 23 22 18 19 15 14 17 16 12 13 1 0 4 5 2 3 88 89 85 84 87 86 94 95 91 90 93 92 75 74 77 76 72 73 81 80 83 82 78 79 34 35 31 30 33 32 44 45 42 43 47 46 25 24 28 29 26 27 39 38 41 40 36 37) #(68 69 66 67 71 70 58 59 55 54 57 56 52 53 49 48 51 50 65 64 63 62 61 60 110 111 108 109 113 112 104 105 102 103 107 106 98 99 96 97 101 100 119 118 117 116 115 114 34 35 31 30 33 32 44 45 42 43 47 46 25 24 28 29 26 27 39 38 41 40 36 37 10 11 7 6 9 8 20 21 18 19 23 22 1 0 4 5 2 3 15 14 17 16 12 13 89 88 87 86 85 84 95 94 93 92 91 90 81 80 83 82 78 79 75 74 77 76 72 73) #(69 68 71 70 66 67 59 58 57 56 55 54 65 64 63 62 61 60 52 53 49 48 51 50 111 110 113 112 108 109 105 104 107 106 102 103 119 118 117 116 115 114 98 99 96 97 101 100 35 34 33 32 31 30 45 44 47 46 42 43 39 38 41 40 36 37 25 24 28 29 26 27 89 88 87 86 85 84 95 94 93 92 91 90 81 80 83 82 78 79 75 74 77 76 72 73 10 11 7 6 9 8 20 21 18 19 23 22 1 0 4 5 2 3 15 14 17 16 12 13) #(70 71 67 66 69 68 64 65 61 60 63 62 53 52 51 50 49 48 59 58 57 56 55 54 112 113 109 108 111 110 118 119 115 114 117 116 99 98 101 100 96 97 105 104 107 106 102 103 88 89 85 84 87 86 94 95 91 90 93 92 75 74 77 76 72 73 81 80 83 82 78 79 11 10 9 8 7 6 21 20 23 22 18 19 15 14 17 16 12 13 1 0 4 5 2 3 35 34 33 32 31 30 45 44 47 46 42 43 39 38 41 40 36 37 25 24 28 29 26 27) #(71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 113 112 111 110 109 108 119 118 117 116 115 114 105 104 107 106 102 103 99 98 101 100 96 97 89 88 87 86 85 84 95 94 93 92 91 90 81 80 83 82 78 79 75 74 77 76 72 73 35 34 33 32 31 30 45 44 47 46 42 43 39 38 41 40 36 37 25 24 28 29 26 27 11 10 9 8 7 6 21 20 23 22 18 19 15 14 17 16 12 13 1 0 4 5 2 3) #(72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 12 13 14 15 16 17 2 3 0 1 5 4 8 9 6 7 11 10 22 23 19 18 21 20 36 37 38 39 40 41 26 27 24 25 29 28 32 33 30 31 35 34 46 47 43 42 45 44 60 61 62 63 64 65 50 51 48 49 53 52 56 57 54 55 59 58 70 71 67 66 69 68 114 115 116 117 118 119 100 101 97 96 99 98 106 107 103 102 105 104 112 113 109 108 111 110) #(73 72 76 77 74 75 79 78 82 83 80 81 90 91 92 93 94 95 84 85 86 87 88 89 13 12 16 17 14 15 3 2 5 4 0 1 22 23 19 18 21 20 8 9 6 7 11 10 37 36 40 41 38 39 27 26 29 28 24 25 46 47 43 42 45 44 32 33 30 31 35 34 114 115 116 117 118 119 100 101 97 96 99 98 106 107 103 102 105 104 112 113 109 108 111 110 60 61 62 63 64 65 50 51 48 49 53 52 56 57 54 55 59 58 70 71 67 66 69 68) #(74 75 72 73 77 76 84 85 86 87 88 89 78 79 80 81 82 83 91 90 94 95 92 93 14 15 12 13 17 16 8 9 6 7 11 10 2 3 0 1 5 4 23 22 21 20 19 18 60 61 62 63 64 65 50 51 48 49 53 52 56 57 54 55 59 58 70 71 67 66 69 68 36 37 38 39 40 41 26 27 24 25 29 28 32 33 30 31 35 34 46 47 43 42 45 44 115 114 118 119 116 117 101 100 99 98 97 96 112 113 109 108 111 110 106 107 103 102 105 104) #(75 74 77 76 72 73 85 84 88 89 86 87 91 90 94 95 92 93 78 79 80 81 82 83 15 14 17 16 12 13 9 8 11 10 6 7 23 22 21 20 19 18 2 3 0 1 5 4 61 60 64 65 62 63 51 50 53 52 48 49 70 71 67 66 69 68 56 57 54 55 59 58 115 114 118 119 116 117 101 100 99 98 97 96 112 113 109 108 111 110 106 107 103 102 105 104 36 37 38 39 40 41 26 27 24 25 29 28 32 33 30 31 35 34 46 47 43 42 45 44) #(76 77 73 72 75 74 90 91 92 93 94 95 79 78 82 83 80 81 85 84 88 89 86 87 16 17 13 12 15 14 22 23 19 18 21 20 3 2 5 4 0 1 9 8 11 10 6 7 114 115 116 117 118 119 100 101 97 96 99 98 106 107 103 102 105 104 112 113 109 108 111 110 37 36 40 41 38 39 27 26 29 28 24 25 46 47 43 42 45 44 32 33 30 31 35 34 61 60 64 65 62 63 51 50 53 52 48 49 70 71 67 66 69 68 56 57 54 55 59 58) #(77 76 75 74 73 72 91 90 94 95 92 93 85 84 88 89 86 87 79 78 82 83 80 81 17 16 15 14 13 12 23 22 21 20 19 18 9 8 11 10 6 7 3 2 5 4 0 1 115 114 118 119 116 117 101 100 99 98 97 96 112 113 109 108 111 110 106 107 103 102 105 104 61 60 64 65 62 63 51 50 53 52 48 49 70 71 67 66 69 68 56 57 54 55 59 58 37 36 40 41 38 39 27 26 29 28 24 25 46 47 43 42 45 44 32 33 30 31 35 34) #(78 79 80 81 82 83 72 73 74 75 76 77 86 87 84 85 89 88 92 93 90 91 95 94 36 37 38 39 40 41 26 27 24 25 29 28 32 33 30 31 35 34 46 47 43 42 45 44 12 13 14 15 16 17 2 3 0 1 5 4 8 9 6 7 11 10 22 23 19 18 21 20 62 63 60 61 65 64 56 57 54 55 59 58 50 51 48 49 53 52 71 70 69 68 67 66 116 117 114 115 119 118 106 107 103 102 105 104 100 101 97 96 99 98 113 112 111 110 109 108) #(79 78 82 83 80 81 73 72 76 77 74 75 92 93 90 91 95 94 86 87 84 85 89 88 37 36 40 41 38 39 27 26 29 28 24 25 46 47 43 42 45 44 32 33 30 31 35 34 13 12 16 17 14 15 3 2 5 4 0 1 22 23 19 18 21 20 8 9 6 7 11 10 116 117 114 115 119 118 106 107 103 102 105 104 100 101 97 96 99 98 113 112 111 110 109 108 62 63 60 61 65 64 56 57 54 55 59 58 50 51 48 49 53 52 71 70 69 68 67 66) #(80 81 78 79 83 82 86 87 84 85 89 88 72 73 74 75 76 77 93 92 95 94 90 91 38 39 36 37 41 40 32 33 30 31 35 34 26 27 24 25 29 28 47 46 45 44 43 42 62 63 60 61 65 64 56 57 54 55 59 58 50 51 48 49 53 52 71 70 69 68 67 66 12 13 14 15 16 17 2 3 0 1 5 4 8 9 6 7 11 10 22 23 19 18 21 20 117 116 119 118 114 115 107 106 105 104 103 102 113 112 111 110 109 108 100 101 97 96 99 98) #(81 80 83 82 78 79 87 86 89 88 84 85 93 92 95 94 90 91 72 73 74 75 76 77 39 38 41 40 36 37 33 32 35 34 30 31 47 46 45 44 43 42 26 27 24 25 29 28 63 62 65 64 60 61 57 56 59 58 54 55 71 70 69 68 67 66 50 51 48 49 53 52 117 116 119 118 114 115 107 106 105 104 103 102 113 112 111 110 109 108 100 101 97 96 99 98 12 13 14 15 16 17 2 3 0 1 5 4 8 9 6 7 11 10 22 23 19 18 21 20) #(82 83 79 78 81 80 92 93 90 91 95 94 73 72 76 77 74 75 87 86 89 88 84 85 40 41 37 36 39 38 46 47 43 42 45 44 27 26 29 28 24 25 33 32 35 34 30 31 116 117 114 115 119 118 106 107 103 102 105 104 100 101 97 96 99 98 113 112 111 110 109 108 13 12 16 17 14 15 3 2 5 4 0 1 22 23 19 18 21 20 8 9 6 7 11 10 63 62 65 64 60 61 57 56 59 58 54 55 71 70 69 68 67 66 50 51 48 49 53 52) #(83 82 81 80 79 78 93 92 95 94 90 91 87 86 89 88 84 85 73 72 76 77 74 75 41 40 39 38 37 36 47 46 45 44 43 42 33 32 35 34 30 31 27 26 29 28 24 25 117 116 119 118 114 115 107 106 105 104 103 102 113 112 111 110 109 108 100 101 97 96 99 98 63 62 65 64 60 61 57 56 59 58 54 55 71 70 69 68 67 66 50 51 48 49 53 52 13 12 16 17 14 15 3 2 5 4 0 1 22 23 19 18 21 20 8 9 6 7 11 10) #(84 85 86 87 88 89 74 75 72 73 77 76 80 81 78 79 83 82 94 95 91 90 93 92 60 61 62 63 64 65 50 51 48 49 53 52 56 57 54 55 59 58 70 71 67 66 69 68 14 15 12 13 17 16 8 9 6 7 11 10 2 3 0 1 5 4 23 22 21 20 19 18 38 39 36 37 41 40 32 33 30 31 35 34 26 27 24 25 29 28 47 46 45 44 43 42 118 119 115 114 117 116 112 113 109 108 111 110 101 100 99 98 97 96 107 106 105 104 103 102) #(85 84 88 89 86 87 75 74 77 76 72 73 94 95 91 90 93 92 80 81 78 79 83 82 61 60 64 65 62 63 51 50 53 52 48 49 70 71 67 66 69 68 56 57 54 55 59 58 15 14 17 16 12 13 9 8 11 10 6 7 23 22 21 20 19 18 2 3 0 1 5 4 118 119 115 114 117 116 112 113 109 108 111 110 101 100 99 98 97 96 107 106 105 104 103 102 38 39 36 37 41 40 32 33 30 31 35 34 26 27 24 25 29 28 47 46 45 44 43 42) #(86 87 84 85 89 88 80 81 78 79 83 82 74 75 72 73 77 76 95 94 93 92 91 90 62 63 60 61 65 64 56 57 54 55 59 58 50 51 48 49 53 52 71 70 69 68 67 66 38 39 36 37 41 40 32 33 30 31 35 34 26 27 24 25 29 28 47 46 45 44 43 42 14 15 12 13 17 16 8 9 6 7 11 10 2 3 0 1 5 4 23 22 21 20 19 18 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96) #(87 86 89 88 84 85 81 80 83 82 78 79 95 94 93 92 91 90 74 75 72 73 77 76 63 62 65 64 60 61 57 56 59 58 54 55 71 70 69 68 67 66 50 51 48 49 53 52 39 38 41 40 36 37 33 32 35 34 30 31 47 46 45 44 43 42 26 27 24 25 29 28 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 14 15 12 13 17 16 8 9 6 7 11 10 2 3 0 1 5 4 23 22 21 20 19 18) #(88 89 85 84 87 86 94 95 91 90 93 92 75 74 77 76 72 73 81 80 83 82 78 79 64 65 61 60 63 62 70 71 67 66 69 68 51 50 53 52 48 49 57 56 59 58 54 55 118 119 115 114 117 116 112 113 109 108 111 110 101 100 99 98 97 96 107 106 105 104 103 102 15 14 17 16 12 13 9 8 11 10 6 7 23 22 21 20 19 18 2 3 0 1 5 4 39 38 41 40 36 37 33 32 35 34 30 31 47 46 45 44 43 42 26 27 24 25 29 28) #(89 88 87 86 85 84 95 94 93 92 91 90 81 80 83 82 78 79 75 74 77 76 72 73 65 64 63 62 61 60 71 70 69 68 67 66 57 56 59 58 54 55 51 50 53 52 48 49 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 39 38 41 40 36 37 33 32 35 34 30 31 47 46 45 44 43 42 26 27 24 25 29 28 15 14 17 16 12 13 9 8 11 10 6 7 23 22 21 20 19 18 2 3 0 1 5 4) #(90 91 92 93 94 95 76 77 73 72 75 74 82 83 79 78 81 80 88 89 85 84 87 86 114 115 116 117 118 119 100 101 97 96 99 98 106 107 103 102 105 104 112 113 109 108 111 110 16 17 13 12 15 14 22 23 19 18 21 20 3 2 5 4 0 1 9 8 11 10 6 7 40 41 37 36 39 38 46 47 43 42 45 44 27 26 29 28 24 25 33 32 35 34 30 31 64 65 61 60 63 62 70 71 67 66 69 68 51 50 53 52 48 49 57 56 59 58 54 55) #(91 90 94 95 92 93 77 76 75 74 73 72 88 89 85 84 87 86 82 83 79 78 81 80 115 114 118 119 116 117 101 100 99 98 97 96 112 113 109 108 111 110 106 107 103 102 105 104 17 16 15 14 13 12 23 22 21 20 19 18 9 8 11 10 6 7 3 2 5 4 0 1 64 65 61 60 63 62 70 71 67 66 69 68 51 50 53 52 48 49 57 56 59 58 54 55 40 41 37 36 39 38 46 47 43 42 45 44 27 26 29 28 24 25 33 32 35 34 30 31) #(92 93 90 91 95 94 82 83 79 78 81 80 76 77 73 72 75 74 89 88 87 86 85 84 116 117 114 115 119 118 106 107 103 102 105 104 100 101 97 96 99 98 113 112 111 110 109 108 40 41 37 36 39 38 46 47 43 42 45 44 27 26 29 28 24 25 33 32 35 34 30 31 16 17 13 12 15 14 22 23 19 18 21 20 3 2 5 4 0 1 9 8 11 10 6 7 65 64 63 62 61 60 71 70 69 68 67 66 57 56 59 58 54 55 51 50 53 52 48 49) #(93 92 95 94 90 91 83 82 81 80 79 78 89 88 87 86 85 84 76 77 73 72 75 74 117 116 119 118 114 115 107 106 105 104 103 102 113 112 111 110 109 108 100 101 97 96 99 98 41 40 39 38 37 36 47 46 45 44 43 42 33 32 35 34 30 31 27 26 29 28 24 25 65 64 63 62 61 60 71 70 69 68 67 66 57 56 59 58 54 55 51 50 53 52 48 49 16 17 13 12 15 14 22 23 19 18 21 20 3 2 5 4 0 1 9 8 11 10 6 7) #(94 95 91 90 93 92 88 89 85 84 87 86 77 76 75 74 73 72 83 82 81 80 79 78 118 119 115 114 117 116 112 113 109 108 111 110 101 100 99 98 97 96 107 106 105 104 103 102 64 65 61 60 63 62 70 71 67 66 69 68 51 50 53 52 48 49 57 56 59 58 54 55 17 16 15 14 13 12 23 22 21 20 19 18 9 8 11 10 6 7 3 2 5 4 0 1 41 40 39 38 37 36 47 46 45 44 43 42 33 32 35 34 30 31 27 26 29 28 24 25) #(95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 65 64 63 62 61 60 71 70 69 68 67 66 57 56 59 58 54 55 51 50 53 52 48 49 41 40 39 38 37 36 47 46 45 44 43 42 33 32 35 34 30 31 27 26 29 28 24 25 17 16 15 14 13 12 23 22 21 20 19 18 9 8 11 10 6 7 3 2 5 4 0 1) #(96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 18 19 20 21 22 23 4 5 1 0 3 2 10 11 7 6 9 8 16 17 13 12 15 14 42 43 44 45 46 47 28 29 25 24 27 26 34 35 31 30 33 32 40 41 37 36 39 38 66 67 68 69 70 71 52 53 49 48 51 50 58 59 55 54 57 56 64 65 61 60 63 62 90 91 92 93 94 95 76 77 73 72 75 74 82 83 79 78 81 80 88 89 85 84 87 86) #(97 96 100 101 98 99 103 102 106 107 104 105 114 115 116 117 118 119 108 109 110 111 112 113 19 18 22 23 20 21 5 4 3 2 1 0 16 17 13 12 15 14 10 11 7 6 9 8 43 42 46 47 44 45 29 28 27 26 25 24 40 41 37 36 39 38 34 35 31 30 33 32 90 91 92 93 94 95 76 77 73 72 75 74 82 83 79 78 81 80 88 89 85 84 87 86 66 67 68 69 70 71 52 53 49 48 51 50 58 59 55 54 57 56 64 65 61 60 63 62) #(98 99 96 97 101 100 108 109 110 111 112 113 102 103 104 105 106 107 115 114 118 119 116 117 20 21 18 19 23 22 10 11 7 6 9 8 4 5 1 0 3 2 17 16 15 14 13 12 66 67 68 69 70 71 52 53 49 48 51 50 58 59 55 54 57 56 64 65 61 60 63 62 42 43 44 45 46 47 28 29 25 24 27 26 34 35 31 30 33 32 40 41 37 36 39 38 91 90 94 95 92 93 77 76 75 74 73 72 88 89 85 84 87 86 82 83 79 78 81 80) #(99 98 101 100 96 97 109 108 112 113 110 111 115 114 118 119 116 117 102 103 104 105 106 107 21 20 23 22 18 19 11 10 9 8 7 6 17 16 15 14 13 12 4 5 1 0 3 2 67 66 70 71 68 69 53 52 51 50 49 48 64 65 61 60 63 62 58 59 55 54 57 56 91 90 94 95 92 93 77 76 75 74 73 72 88 89 85 84 87 86 82 83 79 78 81 80 42 43 44 45 46 47 28 29 25 24 27 26 34 35 31 30 33 32 40 41 37 36 39 38) #(100 101 97 96 99 98 114 115 116 117 118 119 103 102 106 107 104 105 109 108 112 113 110 111 22 23 19 18 21 20 16 17 13 12 15 14 5 4 3 2 1 0 11 10 9 8 7 6 90 91 92 93 94 95 76 77 73 72 75 74 82 83 79 78 81 80 88 89 85 84 87 86 43 42 46 47 44 45 29 28 27 26 25 24 40 41 37 36 39 38 34 35 31 30 33 32 67 66 70 71 68 69 53 52 51 50 49 48 64 65 61 60 63 62 58 59 55 54 57 56) #(101 100 99 98 97 96 115 114 118 119 116 117 109 108 112 113 110 111 103 102 106 107 104 105 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 91 90 94 95 92 93 77 76 75 74 73 72 88 89 85 84 87 86 82 83 79 78 81 80 67 66 70 71 68 69 53 52 51 50 49 48 64 65 61 60 63 62 58 59 55 54 57 56 43 42 46 47 44 45 29 28 27 26 25 24 40 41 37 36 39 38 34 35 31 30 33 32) #(102 103 104 105 106 107 96 97 98 99 100 101 110 111 108 109 113 112 116 117 114 115 119 118 42 43 44 45 46 47 28 29 25 24 27 26 34 35 31 30 33 32 40 41 37 36 39 38 18 19 20 21 22 23 4 5 1 0 3 2 10 11 7 6 9 8 16 17 13 12 15 14 68 69 66 67 71 70 58 59 55 54 57 56 52 53 49 48 51 50 65 64 63 62 61 60 92 93 90 91 95 94 82 83 79 78 81 80 76 77 73 72 75 74 89 88 87 86 85 84) #(103 102 106 107 104 105 97 96 100 101 98 99 116 117 114 115 119 118 110 111 108 109 113 112 43 42 46 47 44 45 29 28 27 26 25 24 40 41 37 36 39 38 34 35 31 30 33 32 19 18 22 23 20 21 5 4 3 2 1 0 16 17 13 12 15 14 10 11 7 6 9 8 92 93 90 91 95 94 82 83 79 78 81 80 76 77 73 72 75 74 89 88 87 86 85 84 68 69 66 67 71 70 58 59 55 54 57 56 52 53 49 48 51 50 65 64 63 62 61 60) #(104 105 102 103 107 106 110 111 108 109 113 112 96 97 98 99 100 101 117 116 119 118 114 115 44 45 42 43 47 46 34 35 31 30 33 32 28 29 25 24 27 26 41 40 39 38 37 36 68 69 66 67 71 70 58 59 55 54 57 56 52 53 49 48 51 50 65 64 63 62 61 60 18 19 20 21 22 23 4 5 1 0 3 2 10 11 7 6 9 8 16 17 13 12 15 14 93 92 95 94 90 91 83 82 81 80 79 78 89 88 87 86 85 84 76 77 73 72 75 74) #(105 104 107 106 102 103 111 110 113 112 108 109 117 116 119 118 114 115 96 97 98 99 100 101 45 44 47 46 42 43 35 34 33 32 31 30 41 40 39 38 37 36 28 29 25 24 27 26 69 68 71 70 66 67 59 58 57 56 55 54 65 64 63 62 61 60 52 53 49 48 51 50 93 92 95 94 90 91 83 82 81 80 79 78 89 88 87 86 85 84 76 77 73 72 75 74 18 19 20 21 22 23 4 5 1 0 3 2 10 11 7 6 9 8 16 17 13 12 15 14) #(106 107 103 102 105 104 116 117 114 115 119 118 97 96 100 101 98 99 111 110 113 112 108 109 46 47 43 42 45 44 40 41 37 36 39 38 29 28 27 26 25 24 35 34 33 32 31 30 92 93 90 91 95 94 82 83 79 78 81 80 76 77 73 72 75 74 89 88 87 86 85 84 19 18 22 23 20 21 5 4 3 2 1 0 16 17 13 12 15 14 10 11 7 6 9 8 69 68 71 70 66 67 59 58 57 56 55 54 65 64 63 62 61 60 52 53 49 48 51 50) #(107 106 105 104 103 102 117 116 119 118 114 115 111 110 113 112 108 109 97 96 100 101 98 99 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 93 92 95 94 90 91 83 82 81 80 79 78 89 88 87 86 85 84 76 77 73 72 75 74 69 68 71 70 66 67 59 58 57 56 55 54 65 64 63 62 61 60 52 53 49 48 51 50 19 18 22 23 20 21 5 4 3 2 1 0 16 17 13 12 15 14 10 11 7 6 9 8) #(108 109 110 111 112 113 98 99 96 97 101 100 104 105 102 103 107 106 118 119 115 114 117 116 66 67 68 69 70 71 52 53 49 48 51 50 58 59 55 54 57 56 64 65 61 60 63 62 20 21 18 19 23 22 10 11 7 6 9 8 4 5 1 0 3 2 17 16 15 14 13 12 44 45 42 43 47 46 34 35 31 30 33 32 28 29 25 24 27 26 41 40 39 38 37 36 94 95 91 90 93 92 88 89 85 84 87 86 77 76 75 74 73 72 83 82 81 80 79 78) #(109 108 112 113 110 111 99 98 101 100 96 97 118 119 115 114 117 116 104 105 102 103 107 106 67 66 70 71 68 69 53 52 51 50 49 48 64 65 61 60 63 62 58 59 55 54 57 56 21 20 23 22 18 19 11 10 9 8 7 6 17 16 15 14 13 12 4 5 1 0 3 2 94 95 91 90 93 92 88 89 85 84 87 86 77 76 75 74 73 72 83 82 81 80 79 78 44 45 42 43 47 46 34 35 31 30 33 32 28 29 25 24 27 26 41 40 39 38 37 36) #(110 111 108 109 113 112 104 105 102 103 107 106 98 99 96 97 101 100 119 118 117 116 115 114 68 69 66 67 71 70 58 59 55 54 57 56 52 53 49 48 51 50 65 64 63 62 61 60 44 45 42 43 47 46 34 35 31 30 33 32 28 29 25 24 27 26 41 40 39 38 37 36 20 21 18 19 23 22 10 11 7 6 9 8 4 5 1 0 3 2 17 16 15 14 13 12 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72) #(111 110 113 112 108 109 105 104 107 106 102 103 119 118 117 116 115 114 98 99 96 97 101 100 69 68 71 70 66 67 59 58 57 56 55 54 65 64 63 62 61 60 52 53 49 48 51 50 45 44 47 46 42 43 35 34 33 32 31 30 41 40 39 38 37 36 28 29 25 24 27 26 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 20 21 18 19 23 22 10 11 7 6 9 8 4 5 1 0 3 2 17 16 15 14 13 12) #(112 113 109 108 111 110 118 119 115 114 117 116 99 98 101 100 96 97 105 104 107 106 102 103 70 71 67 66 69 68 64 65 61 60 63 62 53 52 51 50 49 48 59 58 57 56 55 54 94 95 91 90 93 92 88 89 85 84 87 86 77 76 75 74 73 72 83 82 81 80 79 78 21 20 23 22 18 19 11 10 9 8 7 6 17 16 15 14 13 12 4 5 1 0 3 2 45 44 47 46 42 43 35 34 33 32 31 30 41 40 39 38 37 36 28 29 25 24 27 26) #(113 112 111 110 109 108 119 118 117 116 115 114 105 104 107 106 102 103 99 98 101 100 96 97 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 45 44 47 46 42 43 35 34 33 32 31 30 41 40 39 38 37 36 28 29 25 24 27 26 21 20 23 22 18 19 11 10 9 8 7 6 17 16 15 14 13 12 4 5 1 0 3 2) #(114 115 116 117 118 119 100 101 97 96 99 98 106 107 103 102 105 104 112 113 109 108 111 110 90 91 92 93 94 95 76 77 73 72 75 74 82 83 79 78 81 80 88 89 85 84 87 86 22 23 19 18 21 20 16 17 13 12 15 14 5 4 3 2 1 0 11 10 9 8 7 6 46 47 43 42 45 44 40 41 37 36 39 38 29 28 27 26 25 24 35 34 33 32 31 30 70 71 67 66 69 68 64 65 61 60 63 62 53 52 51 50 49 48 59 58 57 56 55 54) #(115 114 118 119 116 117 101 100 99 98 97 96 112 113 109 108 111 110 106 107 103 102 105 104 91 90 94 95 92 93 77 76 75 74 73 72 88 89 85 84 87 86 82 83 79 78 81 80 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 70 71 67 66 69 68 64 65 61 60 63 62 53 52 51 50 49 48 59 58 57 56 55 54 46 47 43 42 45 44 40 41 37 36 39 38 29 28 27 26 25 24 35 34 33 32 31 30) #(116 117 114 115 119 118 106 107 103 102 105 104 100 101 97 96 99 98 113 112 111 110 109 108 92 93 90 91 95 94 82 83 79 78 81 80 76 77 73 72 75 74 89 88 87 86 85 84 46 47 43 42 45 44 40 41 37 36 39 38 29 28 27 26 25 24 35 34 33 32 31 30 22 23 19 18 21 20 16 17 13 12 15 14 5 4 3 2 1 0 11 10 9 8 7 6 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48) #(117 116 119 118 114 115 107 106 105 104 103 102 113 112 111 110 109 108 100 101 97 96 99 98 93 92 95 94 90 91 83 82 81 80 79 78 89 88 87 86 85 84 76 77 73 72 75 74 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 22 23 19 18 21 20 16 17 13 12 15 14 5 4 3 2 1 0 11 10 9 8 7 6) #(118 119 115 114 117 116 112 113 109 108 111 110 101 100 99 98 97 96 107 106 105 104 103 102 94 95 91 90 93 92 88 89 85 84 87 86 77 76 75 74 73 72 83 82 81 80 79 78 70 71 67 66 69 68 64 65 61 60 63 62 53 52 51 50 49 48 59 58 57 56 55 54 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24) #(119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Utilities (define (foldr kons knil clst . rest) ; fold-right operation from functional programming (if (null? rest) (let f ((lst clst)) (if (null? lst) knil (kons (car lst) (f (cdr lst))))) (let f ((lsts (cons clst rest))) (if (any null? lsts) knil (apply kons (append! (map car lsts) (list (f (map cdr lsts))))))))) (define (remove l e) (cond ((null? l) '()) ((equal? (car l) e) (remove (cdr l) e)) (else (cons (car l) (remove (cdr l) e))))) (define (permutations items) (if (null? items) '(()) (flatten (map (lambda (element) (map (lambda (permutation) (cons element permutation)) (permutations (remove items element)))) items)))) (define (list-head l n) (reverse (list-tail (reverse l) (- (length l) n)))) ; first n elements of input list (define (iota beg n st) (if (<= n 0) '() (cons beg (iota (+ beg st) (- n 1) st)))) ; arithmetic sequence generation (define (geom beg n st) (if (<= n 0) '() (cons beg (geom (* beg st) (- n 1) st)))) ; geometric sequence generation (define (curry f . c) (lambda x (apply f (append c x)))) ; curry operation from functional programming (define (mappnd . c) (foldr append '() c)) ; built-in append in 2-ary :( (define flatten (curry apply mappnd)) ; flatten a list of lists into simple list (define l2v list->vector) ; shorthand for list->vector (define v2l vector->list) ; shorthand for vector->list (define vs! vector-set!) ; shorthand for vector-set! (define vr vector-ref) ; shorthand for vector-ref (define lr list-ref) ; shorthand for list-ref ; Operations in S5 ;(define s5members (permutations (iota 0 5 1))) ; list of members of S5 ;(define (gmul x y) (map (lambda (z) (lr x (lr y z))) (iota 0 5 1))) ; multiply two S5 members ;(define (ginv a) (let ((b (make-vector 5))) (for-each (lambda (x) (vs! b (lr a x) x)) (iota 0 5 1)) (v2l b))) ; compute inverse of S5 member ;(define s5table ; hashtable of S5 members with 7-bit value ; (let ((ht (make-hashtable length equal?))) (for-each (lambda (x) (hashtable-set! ht (lr s5members x) x)) (iota 0 120 1)) ht)) ;(define (from7b x) (lr s5members x)) ; convert S5 member from 7-bit ;(define (to7b x) (hashtable-ref s5table x #f)) ; convert S5 member to 7-bit ;(define s5multbl (l2v (map (lambda (x) (l2v (map (lambda (y) (to7b (gmul x y))) s5members))) s5members))) ; compute S5 multiplication table for 7-bit ;(define s5invtbl (l2v (map (lambda (x) (to7b (ginv x))) s5members))) ; compute S5 inverse table for 7-bit (define (gmul7b x y) (vr (vr s5multbl x) y)) ; look-up multiply two S5 members in 7-bit (define (ginv7b x) (vr s5invtbl x)) ; look-up inverse of S5 member in 7-bit ; Members of S5 used in Barrington transform (define I 0) ; (to7b (list 0 1 2 3 4)) ; x . I = I . x = X (define A 33) ; (to7b (list 1 2 3 4 0)) ; ALPHA CYCLE (define B 71) ; (to7b (list 2 4 3 1 0)) ; BETA CYCLE (define AI 96) ; (ginv7b A) ; A.AI=I (define BI 115) ; (ginv7b B) ; B.BI=I (define G 68) ; (foldr gmul7b I (list A B AI BI)) ; A.B.AI.BI=G (define R 23) ; (to7b (list 0 4 3 2 1)) ; A=R.AI.RI (define RI 23) ; (ginv7b R) ; R.RI=I, R=RI (define AxR 29) ; (gmul7b A R) ; AxR=A.R (define A2B 8) ; (to7b (list 0 2 3 1 4)) ; A2B.A.A2BI=B (define A2BI 12) ; (ginv7b A2B) ; A2B.A2BI=I (define BI2A 11) ; (to7b (list 0 2 4 3 1)) ; BI2A.BI.BI2AI=A (define BI2AI 19) ; (ginv7b BI2A) ; BI2A.BI2AI=I (define G2A 7) ; (to7b (list 0 2 1 4 3)) ; G2A.A.G2AI=G (define G2AI 7) ; (ginv7b G2A) ; G2A.G2AI =I, G2A=G2AI ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Construct group program elements: (input index, group member if false, group member if true) (define (mbk a) (list (list 0 a a))) ; multiplier block (define (cbk a x) (list (list x I a))) ; compute block, a if x, I otherwise (define (nbk a x) (list (list x a I))) ; compute block negated, I if x, a otherwise ; Transform AND and NOT to group program blocks that alpha-compute, input wires are kept in alpha-compute form (define (gNOT x) (append (mbk AxR) (if (number? x) (cbk A x) x) (mbk RI))) ; convert NOT gate to group program (define (gAND x y) (append ; convert AND gate to group program (mbk G2AI) ; pre-multiply G2AI for G -> A (if (number? x) (cbk A x) x) ; alpha-compute x wire or pass-through (mbk A2B) (if (number? y) (cbk A y) y) (mbk A2BI) ; beta-compute y, via A -> B (mbk RI) (if (number? x) (cbk A x) x) (mbk R) ; alpha-inverse-compute x, via A -> AI (mbk BI2AI) (if (number? y) (cbk A y) y) (mbk BI2A) ; beta-inverse-compute y, via A -> BI (mbk G2A))) ; post-multiply G2A for G -> A ; Convert circuit (fragment) to group program using Barrington transform (define (ckt2gp sexp) (cond ((number? sexp) sexp) ((boolean? sexp) (if (equal? sexp '#t) (mbk A) (mbk I))) ((equal? 'NG (car sexp)) (gNOT (ckt2gp (cadr sexp)))) ((equal? 'AG (car sexp)) (gAND (ckt2gp (cadr sexp)) (ckt2gp (caddr sexp)))) (else (list sexp)))) ; pass through unparsed expression ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Secure Matching ; (define (evalgs s) (foldr gmul7b I s)) ; multiply a sequence of group elements (define (weave p s) (cons (car s) (flatten (map list p (cdr s))))) ; weave the publisher and subscriber elements (define (blind l d r) (map (lambda (x y z) (gmul7b (gmul7b x y) z)) l d r)) ; blind a sequence with left and right blinders (define (i2bools len i) (map (lambda (x) (if (equal? (mod (div i x) 2) 0) '#f '#t)) (geom 1 len 2))) ; convert integer to list of booleans, LSB first (define (make-list s n) (if (<= n 0) '() (cons s (make-list s (- n 1))))) ; make a list with s repeated n times (define (evens s) (if (null? s) '() (cons (car s) (if (null? (cdr s)) '() (evens (cddr s)))))) ; list of even indexed elements (define (initrng sd) #t) ; placeholder: seed random number generator (define (next-randseq rng l) ; random sequence of length l from 0..119 (map (lambda (x) (mod x 120)) (prngmore l))) ; Subscriber blinds predicate group program for secure matching (define (combinable? ln) (and (equal? 0 (car ln)) (equal? (cadr ln) (caddr ln)))) ; test if constant group program element (define (pubelt? ln) (and (number? (car ln)) (not (combinable? ln)))) ; test if group program element is from publisher (define (pubrefs n s) (if (equal? s '()) n (if (pubelt? (car s)) (pubrefs (+ n 1) (cdr s)) (pubrefs n (cdr s))))) ; count references to publisher bits in group program (define (selectorgp n b) ; create select group program to pick index b of n bits (flatten (map (lambda (x) (if (equal? x b) (append (mbk G2AI) (cbk A x) (mbk B) (cbk AI x) (mbk BI) (mbk G2A)) (append (cbk A x) (mbk I) (cbk AI x) (mbk I)))) (iota 0 n 1)))) (define (selectorize n s) (flatten (map (lambda (x) (if (pubelt? x) (selectorgp n (car x)) (list x))) s))) ; make selector block for publisher group program element (define (dummypad n l) (flatten (make-list (selectorgp n n) l))) ; make a dummy group program with l blocks, n pub bits (define (canonicalize acc sgp) ; reduce to SPSP ... SPS form by combining subscriber elements (cond ((equal? sgp '()) (list acc)) ((pubelt? (car sgp)) (append (list acc) (canonicalize I (cdr sgp)))) ((combinable? (car sgp)) (canonicalize (gmul7b acc (cadr (car sgp))) (cdr sgp))) (else (error "Unexpected")))) (define (subblind bs npbits nsgpairs sgp) ; subscriber prepares and blinds interest (group program) (let ((padlen (- nsgpairs (pubrefs 0 sgp)))) (if (or (< padlen 0) (not (equal? (length bs) (* 4 npbits nsgpairs)))) (error "Incorrect length") (blind (append (list I) (evens (cdr bs))) (canonicalize I (append (selectorize npbits sgp) (dummypad npbits padlen))) (append (map ginv7b (evens bs)) (list I)))))) ; Publisher blinds metadata bits for secure matching (define (pubblind bs npbits nsgpairs mdata) (if (not (and (equal? (length mdata) npbits) (equal? (length bs) (* 4 npbits nsgpairs)))) (error "Incorrect length") (blind (evens bs) (flatten (make-list (flatten (map (lambda (x) (if (equal? x '#t) (list A AI) (list I I))) mdata)) nsgpairs)) (map ginv7b (evens (cdr bs)))))) ; Broker performs a match given blinded sequences, assumes same secret was used (define (match p s) (let ((v (evalgs (weave p s)))) (cond ((equal? v A) '#t) ((equal? v I) '#f) (else (error "Not alpha-computing"))))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (define (test-securematch) (let* ((n 3) (l 24) (rg (initrng 0)) (r (next-randseq rg (* 4 n l))) (g1 (ckt2gp '(NG 0))) (g2 (ckt2gp '(AG 0 1)))) (display "Testing (proglen: ") (display (+ (* 4 n l) 1)) (display "), expect TFFFFT: ") (for-each (lambda (x) (display (match (pubblind r n l (i2bools n x)) (subblind r n l g1)))) (iota 0 2 1)) (for-each (lambda (x) (display (match (pubblind r n l (i2bools n x)) (subblind r n l g2)))) (iota 0 4 1)) (newline))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Useful circuit building blocks (define (multi-and x) ; AND multi-bit (let* ((fni (length x)) (lfni (floor (/ fni 2)))) (cond ((equal? fni 1) (car x)) ((equal? fni 2) (list 'AG (car x) (cadr x))) (else (list 'AG (multi-and (list-head x lfni)) (multi-and (list-tail x lfni))))))) (define (orflatnext x) (let* ((fni (length x)) (lfni (floor (/ fni 2)))) (cond ((equal? fni 1) (list 'NG (car x))) ((equal? fni 2) (list 'AG (list 'NG (car x)) (list 'NG (cadr x)))) (else (list 'AG (orflatnext (list-head x lfni)) (orflatnext (list-tail x lfni))))))) (define (multi-or x) (list 'NG (orflatnext x))) ; OR multi-bit (define (selbit x a b) (multi-or (list (list 'AG a (list 'NG x)) (list 'AG b x)))) ; IF (select a if x = 0 else b) (define (eqbit a b) (multi-or (list (list 'AG a b) (list 'AG (list 'NG a) (list 'NG b))))) ; EQUAL bit (define (eqckt a b) (multi-and (map (lambda (x) (eqbit (car x) (cadr x))) (map list a b)))) ; EQUAL multi-bit ;(define (gtckt a b)) ; GT (a > b ?)