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
#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <map>
/* #include "/home/bebidek/Kody/simple-console-debug/debug.h" */
using namespace std;

const string precomp = "1210011|0|0|0$1211011|0|0|0$1310012|0|0|0$1311021|0|0$1320021|0|0|0|0|0|0$1321012|0|0|0|0|0|0|0$1410011|1|0|0$1411011|1|0|0$1420032|0|0|0|0|0$1421012|2|0|0|0|0|0|0$1430011|1|0|0|0|0|0|0|0|0|0|0$1431011|1|0|0|0|0|0|0|0|0|0|0$1510012|1|0|0$1511022|0|0$1520021|2|1|0|0|0|0$1521012|2|2|0|0|0|0|0$1530021|2|1|0|0|0|0|0|0|0|0$1531012|2|2|0|0|0|0|0|0|0|0|0$1540012|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0$1541022|0|0|0|0|0|0|0|0|0|0|0|0|0|0$1610011|2|0|0$1611011|2|0|0$1620034|2|0|0|0|0$1621012|4|2|1|0|0|0|0$1630011|2|4|2|1|0|0|0|0|0|0|0$1631011|2|4|2|1|0|0|0|0|0|0|0$1640012|4|2|1|0|0|0|0|0|0|0|0|0|0|0|0$1641034|2|0|0|0|0|0|0|0|0|0|0|0|0$1650011|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$1651011|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$1710012|2|0|0$1711023|0|0$1720021|4|4|0|0|0|0$1721012|4|4|2|0|0|0|0$1730022|4|6|4|0|0|0|0|0|0|0$1731012|3|8|3|2|1|0|0|0|0|0|0$1740012|3|8|3|2|1|0|0|0|0|0|0|0|0|0|0$1741022|4|6|4|0|0|0|0|0|0|0|0|0|0|0$1750012|4|4|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$1751021|4|4|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$1760023|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$1761012|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$1810011|3|0|0$1811011|3|0|0$1820036|6|0|0|0|0$1821012|6|4|4|0|0|0|0$1830011|3|8|8|6|2|0|0|0|0|0|0$1831011|3|8|8|6|2|0|0|0|0|0|0$1840012|6|a|a|6|2|2|0|0|0|0|0|0|0|0|0$1841038|8|c|4|0|0|0|0|0|0|0|0|0|0$1850011|3|8|8|6|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0$1851011|3|8|8|6|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0$1860036|6|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$1861012|6|4|4|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$1870011|3|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$1871011|3|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2210022|0|0$2211022|0|0$2220042|0|0|0|0$2221024|0|0|0|0|0|0$2230022|0|0|0|0|0|0|0|0|0|0$2231022|0|0|0|0|0|0|0|0|0|0$2310022|1|0$2311022|1|0$2320042|4|0|0|0$2321022|4|3|0|0|0|0$2330033|4|2|0|1|0|0|0|0|0$2331033|4|2|0|1|0|0|0|0|0$2340022|4|3|0|0|0|0|0|0|0|0|0|0|0|0$2341042|4|0|0|0|0|0|0|0|0|0|0|0$2350022|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2351022|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2410022|2|0$2411022|2|0$2420042|8|2|0|0$2421022|4|6|4|0|0|0$2430032|6|8|6|4|2|0|0|0|0$2431032|6|8|6|4|2|0|0|0|0$2440022|0|8|g|8|0|2|0|2|0|0|0|0|0|0$2441058|c|8|4|0|0|0|0|0|0|0|0$2450032|6|8|6|4|2|0|0|0|0|0|0|0|0|0|0|0|0$2451032|6|8|6|4|2|0|0|0|0|0|0|0|0|0|0|0|0$2460042|8|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2461022|4|6|4|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2470022|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2471022|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2510022|3|0$2511022|3|0$2520042|c|6|0|0$2521022|4|9|8|2|0|0$2530032|6|d|g|c|a|1|0|0|0$2531032|6|d|g|c|a|1|0|0|0$2540022|0|7|k|u|o|b|4|8|4|0|0|0|0|0$2541058|i|w|q|c|4|0|0|0|0|0|0$2550032|4|b|o|w|s|g|4|4|0|1|0|0|0|0|0|0|0$2551032|4|b|o|w|s|g|4|4|0|1|0|0|0|0|0|0|0$2560058|i|w|q|c|4|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2561022|0|7|k|u|o|b|4|8|4|0|0|0|0|0|0|0|0|0|0|0|0|0$2570032|6|d|g|c|a|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2571032|6|d|g|c|a|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2580022|4|9|8|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2581042|c|6|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2610022|4|0$2611022|4|0$2620042|g|c|0|0$2621022|4|c|c|6|0|0$2630032|6|i|q|q|q|6|0|0|0$2631032|6|i|q|q|q|6|0|0|0$2640022|0|8|k|1c|1o|19|s|m|k|2|0|0|0|0$2641058|o|1k|1s|1k|o|8|0|0|0|0|0$2650032|4|e|s|1q|2q|2a|1i|w|a|8|2|0|0|0|0|0|0$2651032|4|e|s|1q|2q|2a|1i|w|a|8|2|0|0|0|0|0|0$2660058|k|1k|2i|3c|2o|14|g|0|4|0|2|0|0|0|0|0|0|0|0$2661022|0|8|g|1a|28|2o|28|1m|14|w|8|6|0|0|0|0|0|0|0|0|0|0$2670032|4|e|s|1q|2q|2a|1i|w|a|8|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2671032|4|e|s|1q|2q|2a|1i|w|a|8|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2680022|0|8|k|1c|1o|19|s|m|k|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2681058|o|1k|1s|1k|o|8|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2710022|5|0$2711022|5|0$2720042|k|k|0|0$2721022|4|f|g|c|0|0$2730032|6|n|10|1a|1e|j|0|0|0$2731032|6|n|10|1a|1e|j|0|0|0$2740022|0|9|k|1u|2o|2w|2c|1m|1o|c|0|0|0|0$2741058|u|28|3a|3o|26|14|4|0|0|0|0$2750032|4|i|u|2j|4w|5s|5q|3p|24|12|i|1|0|0|0|0|0$2751032|4|i|u|2j|4w|5s|5q|3p|24|12|i|1|0|0|0|0|0$2760058|q|20|44|7s|9e|8o|4y|1o|10|8|e|4|0|0|0|0|0|0|0$2761022|0|9|g|1q|2w|5l|7o|78|6g|4r|2s|1s|g|6|0|0|0|0|0|0|0|0$2770032|4|i|s|2j|5c|7s|a0|8h|5k|3w|1g|x|4|6|0|1|0|0|0|0|0|0|0|0|0$2771032|4|i|s|2j|5c|7s|a0|8h|5k|3w|1g|x|4|6|0|1|0|0|0|0|0|0|0|0|0$2780022|0|9|g|1q|2w|5l|7o|78|6g|4r|2s|1s|g|6|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2781058|q|20|44|7s|9e|8o|4y|1o|10|8|e|4|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$2810022|6|0$2811022|6|0$2820042|o|u|0|0$2821022|4|i|k|k|0|0$2830032|6|s|1a|20|2a|18|0|0|0$2831032|6|s|1a|20|2a|18|0|0|0$2840022|0|a|k|2c|3o|58|4s|3q|3w|16|0|0|0|0$2841058|10|2w|58|6o|54|34|o|0|0|0|0$2850032|4|m|w|3e|72|aw|d4|ag|7q|3u|2a|a|0|0|0|0|0$2851032|4|m|w|3e|72|aw|d4|ag|7q|3u|2a|a|0|0|0|0|0$3310024|0|1$3311034|0$3320046|0|a|0|0$3321038|0|c|0|0|0$3330044|0|q|0|a|0|0|0|0$3331034|0|o|0|c|0|4|0|0|0$334004c|0|10|0|d|0|4|0|1|0|0|0|0$334105c|0|10|0|c|0|0|0|0|0|0|0$335004c|0|10|0|d|0|4|0|1|0|0|0|0|0|0|0|0$335105c|0|10|0|c|0|0|0|0|0|0|0|0|0|0|0$3360044|0|q|0|a|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$3361034|0|o|0|c|0|4|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$3370046|0|a|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$3371038|0|c|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$3380024|0|1|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$3381034|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$3410022|3|1$3411022|3|1$3420042|c|a|6|0$3421038|6|a|c|0|0$3430031|4|e|n|q|p|e|3|0|0$3431031|4|e|n|q|p|e|3|0|0$344004a|8|y|1q|1b|12|u|a|e|2|0|0|0$3441052|m|q|1y|1y|q|m|2|0|0|0|0$3450042|9|l|18|29|2k|1v|18|n|7|4|2|0|0|0|0|0$3451042|9|l|18|29|2k|1v|18|n|7|4|2|0|0|0|0|0$3460054|0|1c|24|2m|3g|1w|g|k|0|0|0|2|0|0|0|0|0|0|0$3461032|0|c|u|20|2c|2c|20|1i|w|c|i|0|0|0|0|0|0|0|0|0|0$3470042|9|l|18|29|2k|1v|18|n|7|4|2|0|0|0|0|0|0|0|0|0|0|0|0|0$3471042|9|l|18|29|2k|1v|18|n|7|4|2|0|0|0|0|0|0|0|0|0|0|0|0|0$348004a|8|y|1q|1b|12|u|a|e|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$3481052|m|q|1y|1y|q|m|2|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0$3510024|2|2$3511036|1$3520046|8|o|a|1$3521038|4|o|e|6|0$3530044|2|1a|16|1u|1e|c|2|0$3531032|4|s|t|1i|1b|18|n|0|0$3540048|8|1c|1u|47|3s|2z|2m|16|w|1|0|0$3541056|k|1q|2k|4y|4e|2e|1u|4|0|0|0$3550044|a|u|22|4i|64|82|7k|5a|4q|1a|14|4|0|0|0|0$3551056|8|1u|2y|6g|8u|90|6s|2a|22|g|f|0|0|0|0$3560054|9|18|34|6e|bb|e8|dd|ak|41|2w|q|i|7|6|0|0|0|0|0$3561032|0|4|u|2k|3i|82|bm|c4|bo|88|64|2k|28|a|4|0|0|0|0|0|0$3570052|i|s|30|6m|c8|h8|hu|e2|80|4s|22|12|a|c|4|0|0|0|0|0|0|0|0$3571044|8|k|1o|4o|80|ce|fq|eu|c4|a5|50|2p|18|g|2|0|0|1|0|0|0|0|0|0$3610022|5|2$3611022|5|2$3620042|k|s|k|2$3621038|a|m|u|a|1$3630031|4|g|1g|22|2u|2u|1e|7|0$3631031|4|g|1g|22|2u|2u|1e|7|0$3640048|c|1e|3g|5o|7y|8e|6u|5m|2k|m|0|0$3641052|q|1k|4y|8s|9o|8g|5i|2a|2|0|0$3710024|4|3$3711038|2$3720046|g|1a|s|4$3721038|8|10|10|k|2$3730044|4|1v|2q|4x|5c|2n|m|1$3731032|4|u|1u|32|42|4u|3a|k|0$3740048|8|1o|3w|8l|dm|g3|g8|cu|8a|21|4|0$3741056|o|2k|68|ds|i6|hg|fi|6q|1a|0|0$3810022|7|3$3811022|7|3$3820042|s|1i|16|6$3821038|e|y|1k|s|4$3830031|4|i|29|3u|6j|86|5d|1a|2$3831031|4|i|29|3u|6j|86|5d|1a|2$4410022|4|2$4411022|4|2$4420042|g|k|g|2$4421038|8|g|o|8|0$4430046|g|w|1k|20|1s|u|4|0$4431046|g|w|1k|20|1s|u|4|0$4440048|8|18|2o|3s|4w|4w|3k|2s|14|c|0|0$444106o|1c|3c|5c|60|4w|2g|w|0|0|0$4450058|o|1o|3m|78|b6|c4|aa|74|40|1w|m|4|0|0|0$4451058|o|1o|3m|78|b6|c4|aa|74|40|1w|m|4|0|0|0$4510022|5|3$4511022|5|3$4520042|k|w|u|6$4521038|a|m|12|k|2$4530046|h|1a|2f|3o|4b|2s|q|1$4531046|h|1a|2f|3o|4b|2s|q|1$4540046|c|1g|3c|6d|ai|cy|ce|be|6i|2a|a|0$454106o|1u|52|9q|ea|fi|bu|6a|1i|0|0$4610022|6|4$4611022|6|4$4620042|o|1a|1c|c$4621038|c|s|1i|10|6$4630046|i|1o|3e|5s|7y|6a|28|6$4631046|i|1o|3e|5s|7y|6a|28|6$4710022|7|5$4711022|7|5$4720042|s|1q|1y|k$4721038|e|y|20|1k|c$4730046|j|22|4h|8c|ct|bo|4y|j$4731046|j|22|4h|8c|ct|bo|4y|j$4810022|8|6$4811022|8|6$4820042|w|28|2o|u$4821038|g|14|2k|28|k$4830046|k|2g|5o|bc|j0|ja|98|18$4831046|k|2g|5o|bc|j0|ja|98|18$5510024|4|5$5511038|4$5520046|g|1i|1g|g$5521038|8|10|1g|18|8$5530044|4|1s|3c|64|9o|7i|2s|e$5531048|w|1k|3o|68|8c|7o|3c|8$5610022|7|6$5611022|7|6$5620042|s|1u|2c|u$5621038|e|y|28|1y|j$5630046|j|22|4p|96|fb|fg|7v|16$5631046|j|22|4p|96|fb|fg|7v|16$5710024|6|8$571103a|7$5720046|o|2k|3a|1d$5721038|c|1c|2q|2y|y$5810022|9|9$5811022|9|9$5820042|10|30|4i|20$5821038|i|1a|3m|40|1i$6610022|8|8$6611022|8|8$6620042|w|2g|3k|1k$6621038|g|14|30|34|14$6710022|9|a$6711022|9|a$6720042|10|34|50|2i$6721038|i|1a|3u|4i|1x$6810022|a|c$6811022|a|c$6820042|14|3u|6o|3o$6821038|k|1g|4q|64|2y$7710024|8|d$771103c|c$7720046|w|42|6w|40$7721038|g|1o|4o|6g|38$7810022|b|f$7811022|b|f$7820042|18|4q|96|5u$7821038|m|1m|5w|8k|4w$8810022|c|i$8811022|c|i$8820042|1c|5o|c0|8i$8821038|o|1s|74|bc|7c$2860058|w|2g|62|cg|jq|pc|jq|cg|62|2g|1q|w|2|0|0|0|0|0|0$2861022|0|a|g|28|3g|8s|dw|i4|ks|gk|d8|8c|44|1g|c|0|0|0|0|0|0|0$2870032|4|m|u|3i|78|ec|ns|s0|t6|mm|ea|8m|30|20|e|c|2|0|0|0|0|0|0|0|0$2871032|4|m|u|3i|78|ec|ns|s0|t6|mm|ea|8m|30|20|e|c|2|0|0|0|0|0|0|0|0$3580044|8|k|1o|4o|80|ce|fq|eu|c4|a5|50|2p|18|g|2|0|0|1|0|0|0|0|0|0|0|0|0|0$3581052|i|s|30|6m|c8|h8|hu|e2|80|4s|22|12|a|c|4|0|0|0|0|0|0|0|0|0|0|0|0$3650042|7|l|2g|51|b2|hw|mi|my|hp|ab|5q|2b|a|0|0|0$3651042|7|l|2g|51|b2|hw|mi|my|hp|ab|5q|2b|a|0|0|0$3840048|c|1q|5i|ay|k8|r8|tg|so|hw|5u|i|0$3841052|u|2e|8e|ki|te|wy|ty|hs|48|8|0$4460064|w|2u|7k|aw|j4|q4|j4|aw|7k|2w|1c|o|g|2|0|0|0|0$446105g|g|1s|54|8w|dk|ig|ig|gw|d4|7s|4o|1s|o|0|0|0|0|0|0$4470054|i|10|3a|84|ec|mg|se|rk|mc|f8|8a|44|22|s|8|4|2|0|0|0|0|0|0$4471054|i|10|3a|84|ec|mg|se|rk|mc|f8|8a|44|22|s|8|4|2|0|0|0|0|0|0$4550057|m|26|54|bs|mk|xv|152|12q|tg|if|8m|2j|a|0|0$4640046|c|1k|4c|98|h4|ow|so|u2|l8|98|1o|2$464106o|2c|6w|fc|q4|x4|vo|ls|80|s|0$5540044|g|1g|3k|a5|ig|qy|zw|yz|rs|e2|2o|6$554106w|2s|68|g0|tg|10c|14s|sw|bg|20|0$5730044|6|2c|5u|cc|om|qu|fa|36$5731048|y|2k|66|d0|m2|qw|gi|2t$5830046|l|2u|7f|go|x7|16c|rw|65$5831046|l|2u|7f|go|x7|16c|rw|65$6630046|k|2g|64|d4|os|tm|ik|3u$6631046|k|2g|64|d4|os|tm|ik|3u$2880022|0|a|g|2a|3c|98|fk|nk|vc|so|p4|jo|ao|6y|1k|u|0|6|0|2|0|0|0|0|0|0|0|0|0|0$2881058|w|2g|68|d4|mw|zc|yw|rs|hk|6w|5k|20|1k|8|8|0|0|0|0|0|0|0|0|0|0|0|0$3660054|0|18|3y|90|kg|yu|1as|1f8|140|og|dg|6k|2o|1q|a|0|0|0|0$3661032|0|4|12|2o|5g|do|n8|ww|176|17w|102|s4|hg|72|3i|o|0|0|0|0|0$3750044|8|y|36|7o|hs|u3|16s|1gd|1h2|10p|p2|b8|1y|6|0|0$3751056|8|2k|5g|ew|ua|1b4|1lk|1e6|11e|m4|b4|30|0|0|0$4480044|0|o|1c|4u|a8|ds|mo|wg|rk|mw|k0|ce|6o|34|g|k|0|0|0|2|0|0|0|0|0|0|0|0$448107w|2o|4w|e8|o0|w0|z4|r4|hs|a8|40|28|1s|g|g|0|0|0|0|0|0|0|0|0|0|0$4551057|m|26|54|bs|mk|xv|152|12q|tg|if|8m|2j|a|0|0$474106o|2u|8u|m6|15u|1n6|1ti|1h6|om|48|4$6730046|l|2u|7n|hm|10h|1dg|zn|92$6731046|l|2u|7n|hm|10h|1dg|zn|92$4740046|c|1o|5c|cb|p6|152|1he|1qe|1fe|q6|5y|c$5640044|g|1s|50|ck|rq|1cc|1uu|2bg|24k|190|d8|13$564106o|2u|96|n8|1b2|21k|2g8|27k|17o|am|m$6830046|m|38|9a|mo|1ei|23m|1og|hq$6831046|m|38|9a|mo|1ei|23m|1og|hq$7730044|8|2w|98|m4|1io|28i|1t0|ku$7731048|10|3k|9k|o8|1e0|280|1vk|k4$3670042|5|h|1e|4n|9x|nx|15e|1mh|235|255|1nz|15z|pd|cl|62|25|u|e|1|0|0|0|0|0$3671042|5|h|1e|4n|9x|nx|15e|1mh|235|255|1nz|15z|pd|cl|62|25|u|e|1|0|0|0|0|0$3850042|7|l|3a|83|m2|19n|249|2y4|36l|2nc|1wu|11g|ay|y|0|0$3851042|7|l|3a|83|m2|19n|249|2y4|36l|2nc|1wu|11g|ay|y|0|0$456105c|g|24|64|do|r0|19u|1x2|2g8|2g4|25w|1oc|zc|hk|6m|1e|0|0|0|0$4650056|o|2i|6e|h4|112|1t2|2mk|32w|2x0|28c|1bu|iy|3o|6|0$4651056|o|2i|6e|h4|112|1t2|2mk|32w|2x0|28c|1bu|iy|3o|6|0$4840046|c|1s|6c|fm|yo|1ps|2g0|346|2vo|1nk|fw|16$484106o|3c|aw|u8|1ps|2n4|394|2z4|1ls|d4|o$7830046|n|3m|b9|tc|1z1|3c4|31w|12z$7831046|n|3m|b9|tc|1z1|3c4|31w|12z$3680044|8|o|1s|5a|d8|ok|19o|1yu|2dy|2o2|2jq|1zt|1e8|t0|d0|6o|1o|g|8|b|4|0|0|0|0|0|0|0$3681052|6|y|36|7e|km|14o|1vo|2ss|328|2ki|1xq|182|mu|d8|6m|3u|16|c|2|0|0|0|0|0|0|0|0$4560064|o|3o|a6|ju|17s|216|2lw|2sc|2bg|1fg|ui|fq|70|2e|k|0|0|0$3760054|9|18|4w|cy|vj|1pq|2qy|3n0|3tm|3am|243|15y|ma|98|3j|4|0|0|0$3761032|0|4|s|32|6q|h4|128|1r8|2oo|3ge|3iu|31g|2de|1cu|ne|a8|w|0|0|0|0$555005c|o|2w|8g|ik|12u|1z4|2xa|3r0|3q6|340|21f|uk|70|k|1$555106g|28|54|fw|11c|1yc|364|3t4|3tg|2zo|1wo|wc|7w|g|0$5740044|g|1o|5k|gf|12m|20e|39y|4aj|4k6|35m|136|4i$574106w|3s|b0|vm|20k|39e|4nk|4rm|31u|zy|36$6640044|g|1w|60|g8|13c|268|3ew|4u0|58o|3qk|1fk|6d$664106o|3c|bk|wg|21s|3mo|51s|5g0|3qg|1ag|4w$8830046|o|40|dc|10o|2mw|4wu|4z8|20w$8831046|o|40|dc|10o|2mw|4wu|4z8|20w$4571052|e|15|3o|9s|oj|1e5|2ev|3ne|4p7|50n|4cx|37h|22b|14k|j7|8b|35|v|5|0|0|0|0$4570052|e|15|3o|9s|oj|1e5|2ev|3ne|4p7|50n|4cx|37h|22b|14k|j7|8b|35|v|5|0|0|0|0$4750056|o|2r|7w|mu|1id|2yv|4v9|6kz|77k|6fq|4js|27d|kz|1u|1$4751056|o|2r|7w|mu|1id|2yv|4v9|6kz|77k|6fq|4js|27d|kz|1u|1$5840044|g|20|70|jq|1eg|2xw|4vw|7cc|8i8|6gs|2mc|cs$584106o|3u|dq|15u|2ru|54q|7m6|8sa|6he|2fo|ak$3770052|m|w|3q|bc|wi|1wu|3dv|5fe|77t|7im|6pq|4xs|32d|1t4|y4|c0|5y|o|1|0|0|0|0$3771044|8|g|20|6i|eq|12c|20m|3go|5a4|6ny|7by|6sq|53k|3e2|1vg|qc|cy|48|1s|0|0|0|0|0$4580042|0|k|18|4f|c8|ps|1hu|2s8|4f8|644|73o|7ez|6ma|502|3ae|1ti|su|d6|4m|1s|10|k|2|0|0|0|0|0$458107m|20|6k|k4|17g|2j8|4fk|6f4|7xe|7xe|6gm|4lu|2v2|1my|ye|ga|72|2g|o|0|0|0|0|0|0|0$4660064|k|46|d8|ug|204|3xy|6ek|8j8|98s|82m|5x0|3js|1v0|r0|70|u|0|0$466105c|e|24|7k|i8|154|2a8|40i|66g|7xs|8oo|82e|674|3y0|1yg|oi|4o|0|0|0$3860054|0|1g|56|eo|18g|2lw|4va|7iq|936|92y|7f4|4tw|2po|1ds|fs|2a|0|0|0$3861032|0|4|12|34|8g|nc|1io|2ui|4ua|70m|8im|8sw|7ko|55o|2zo|1d4|dc|c|0|0|0$6740044|g|20|70|k4|1gi|370|5i6|8lg|ais|8me|3x4|mg$674106o|3u|e2|170|2ym|5qk|8w0|avo|8p2|3oy|ja$5650055|m|2u|86|na|1l5|3b8|5w5|8o3|ace|a2k|7xq|4gq|1ih|7j|9$5651055|m|2u|86|na|1l5|3b8|5w5|8o3|ace|a2k|7xq|4gq|1ih|7j|9$5560064|14|3u|ck|zu|22k|43m|7bs|a9q|c1g|bgm|8s8|5pk|34g|1dw|fg|1u|4|0$5561058|g|1s|7c|ic|124|2gc|4ik|72g|9uo|b9w|b0g|97c|648|3e4|1d8|ao|o|0|0$3780044|8|g|1w|68|eu|xk|27m|3ze|6hq|9eu|bcc|c8o|b1m|8gf|5sa|3c1|1kc|pz|88|3z|1m|w|0|0|0|0|0|0$3781052|e|12|3g|as|s2|1u0|3rg|6j2|9ny|c7s|ckg|b5c|86s|56o|338|1p0|si|ea|3s|1c|0|0|0|0|0|0|0$4850056|o|30|9e|sw|22s|4fy|7zk|bzu|em4|en8|bqy|6ls|24q|9m|a$4851056|o|30|9e|sw|22s|4fy|7zk|bzu|em4|en8|bqy|6ls|24q|9m|a$6840044|g|24|80|o8|1v8|4f0|86s|dto|il8|gyk|8po|1nc$684106o|4c|go|1iw|41w|8fc|e6s|j4w|h5k|8dw|1hs$7740044|g|1w|7k|od|1x0|4gq|8s0|ejn|k38|izu|a2o|214$774106w|4s|gw|1is|490|8ko|f6c|ksk|j1w|9so|1ug$4671052|c|14|48|bq|x0|28i|4ki|86o|d4w|i5s|l6u|kve|hdi|cds|7jm|3xm|1r8|mc|5e|k|0|0|0$4670052|c|14|48|bq|x0|28i|4ki|86o|d4w|i5s|l6u|kve|hdi|cds|7jm|3xm|1r8|mc|5e|k|0|0|0$3870042|5|l|1i|5r|fv|1am|2xw|5t8|abm|fjq|jwx|luy|ju3|fbw|a7x|5mp|2n7|151|cb|13|0|0|0|0$3871042|5|l|1i|5r|fv|1am|2xw|5t8|abm|fjq|jwx|luy|ju3|fbw|a7x|5mp|2n7|151|cb|13|0|0|0|0$575005a|s|3g|bw|wk|2ag|53y|9og|g26|lro|ogm|meg|et0|63e|16s|2u$575106g|2m|7o|qw|23t|4x8|9zj|gfo|m4w|oe8|lxx|eoc|69f|18a|20$4760064|k|4i|fw|16e|2zm|6im|c2m|ila|nuu|p8i|m6k|g0u|9qq|4ka|1fm|86|e|0$476105c|c|2a|8q|ma|1lg|3j4|6uy|by2|htu|mpq|one|mdu|gv0|a74|4km|1a2|4i|0|0$6650054|o|34|9m|tw|296|57c|afk|hqw|ops|sd0|qny|ilc|8by|1tg|48$6651054|o|34|9m|tw|296|57c|afk|hqw|ops|sd0|qny|ilc|8by|1tg|48$557106g|20|40|ds|11g|2ds|4x0|9bs|f44|ln4|rl4|trk|qkc|kq0|dd8|7bg|3f4|1bo|fc|28|0|0|0$5570068|c|38|a0|v8|21w|4mk|8zo|fgc|mu0|s8m|tl8|qa2|jtg|dby|7gs|3k6|1hk|cq|18|6|0|0$7840044|g|28|90|sy|2do|65o|cec|mwo|ydo|zu8|lkk|530$784106o|4u|jq|1xe|5ka|clq|nbe|z8y|10by|l2s|4sc$5660064|c|4s|fo|16u|37m|74w|e2y|ntk|xoa|13d0|129c|un4|knq|b4m|46q|wa|2q|2$5661058|e|2g|80|mu|1oa|3pi|7p9|eii|n4s|vxm|128p|124s|vne|ljo|bc5|40o|oy|14|0$4680042|0|g|18|4m|do|yk|2ag|4wa|9mo|gqo|pag|yb9|14tk|16fc|11u8|t0e|j5s|axs|58s|2cc|z0|d8|48|u|0|0|0|0$468107g|28|7g|no|1s4|4ac|8vk|gco|qa8|103o|16m0|1700|10uw|rd8|i34|awo|5y8|2po|124|bw|1w|0|0|0|0|0$3880044|8|o|28|6s|iq|1a6|39c|6j6|c8m|kpe|tpu|120v|1792|15d6|xzq|ojm|esy|7mu|3im|1fo|k8|8o|16|0|0|0|0|0$3881052|6|16|3y|b8|xk|2j2|5sa|c06|kqq|uuu|148q|18cm|14wy|wyi|mxq|e9c|87k|41k|1kw|m6|4u|0|0|0|0|0|0$5850055|m|38|be|10i|2wc|73i|f07|r2y|146k|1dg9|1dzu|11nj|ia4|4fo|c8$5851055|m|38|be|10i|2wc|73i|f07|r2y|146k|1dg9|1dzu|11nj|ia4|4fo|c8$4860064|k|4u|ik|1j2|45o|9ta|jys|y5i|1d8s|1nci|1npg|1dmy|yes|ij4|6ss|1by|3k|2$486105c|c|2c|9o|qw|238|4z0|ajk|k4g|xb8|1bec|1lvk|1ni0|1ews|zh8|its|6ks|12s|1k|0$8840044|g|2c|a0|xw|2xs|868|hlc|yy0|1l68|1u5g|18q0|cbs$884106o|5c|mw|2dc|7bc|hqo|zco|1mf4|1v28|181c|bu8$6750054|o|3b|ba|10w|309|7im|gfl|uyk|1c78|1qav|1uju|1hx0|swr|866|rr$6751054|o|3b|ba|10w|309|7im|gfl|uyk|1c78|1qav|1uju|1hx0|swr|866|rr$558006k|w|3i|bs|yo|284|53a|a80|ini|upk|18cr|1jp0|1pd2|1n9c|1e3s|zik|lym|buo|5g5|2b8|vi|bc|2v|4|0|0|0$558107c|20|9s|mo|1s4|4fc|9no|ido|uf0|19b4|1m8o|1r9c|1neg|1bvo|xsk|lbg|cao|69k|2j4|xk|84|8|0|0|0|0$4771052|c|13|4i|dx|15v|34v|786|eln|qix|16gm|1n2l|1ydb|1zh0|1pz2|19ok|so8|f4v|6fs|1z5|bz|l|0|0$4770052|c|13|4i|dx|15v|34v|786|eln|qix|16gm|1n2l|1ydb|1zh0|1pz2|19ok|so8|f4v|6fs|1z5|bz|l|0|0$5761058|c|22|98|qu|20y|5c8|by8|oj4|189q|1x6w|2l8o|2zqq|2vaw|2ace|1g3a|mwg|5uy|lw|c$5760064|w|4u|ic|1q0|4g2|auy|np8|184v|1ywm|2opk|30vs|2umo|28ds|1ehj|n80|6ex|r8|15$567106a|15|42|dk|16p|36t|7np|gfl|vpt|1iqw|2b8v|3185|3eth|3aua|2pxb|1wf9|14e5|jvd|7bz|1pd|66|7|0$567006a|15|42|dk|16p|36t|7np|gfl|vpt|1iqw|2b8v|3185|3eth|3aua|2pxb|1wf9|14e5|jvd|7bz|1pd|66|7|0$6660064|8|52|iw|1l4|4j4|b68|ow8|1bwg|2768|32js|3lm0|3i7c|2uww|1vyw|wo8|9v0|1dk|22$6661058|c|2g|94|rk|27s|5e0|cc8|q4o|1bv4|24nk|2zi8|3jo0|3jbc|2x54|1x94|wsg|9ac|13c|14$6850054|o|3i|cy|188|3uo|a9s|o1q|1d16|2b6w|39sg|3uvm|3hzu|24xu|pss|33u$6851054|o|3i|cy|188|3uo|a9s|o1q|1d16|2b6w|39sg|3uvm|3hzu|24xu|pss|33u$7750058|w|40|fk|1cs|440|as8|oww|1f0s|2gjm|3jzk|4ayf|40o8|2ir2|vw8|47x$775106g|30|ag|144|3p4|a80|ov8|1g0k|2hgs|3ks8|4a3k|3z9c|2jac|wb4|42g$478107g|2c|80|ru|2cc|690|ekg|uf8|1kh2|2jwa|3ns2|4l06|4yi6|4mw6|3rre|2p6i|1pmw|y9w|ga4|6b6|1s8|ak|0|0|0|0$4780042|0|g|14|4p|g4|15u|31i|7es|g8a|w08|1kjo|2hu4|3jfa|4gya|4x6m|4pae|3w2e|2s76|1pa2|wko|f1s|63m|20e|go|1y|0|0|0$4871052|c|12|4y|fu|1e6|450|aem|myk|19r2|296e|3iyw|4s8y|5lai|5lsg|4sp4|3hie|24gy|11w0|dve|334|a2|8|0$4870052|c|12|4y|fu|1e6|450|aem|myk|19r2|296e|3iyw|4s8y|5lai|5lsg|4sp4|3hie|24gy|11w0|dve|334|a2|8|0$5861058|c|2o|9s|vg|2qu|742|h5m|11ze|2204|3iqw|5a5k|6qv4|7972|6hsi|4nh0|2eyo|rpq|3zw|5u$5860064|c|5c|ky|1xw|5xq|fh4|105o|21ne|3lps|5efq|6uj6|78i8|6efy|4l0m|2eic|slm|4iy|86$7851054|o|3p|eq|1gc|4wb|dzu|zdg|26t7|43pg|6fz8|8igk|8tll|6awn|2l5e|etv$7850054|o|3p|eq|1gc|4wb|dzu|zdg|26t7|43pg|6fz8|8igk|8tll|6awn|2l5e|etv$5681076|1o|7o|sg|2b6|6aw|few|ya8|1w50|3bng|58cu|79l0|8rjg|973y|8ez8|6pwe|4qpi|2xki|1k3e|pa2|8ya|248|7c|0|0|0$568006g|10|3s|es|15u|33k|7k8|hli|10q4|1wym|3bgt|544k|71po|8mmc|97z5|8k0c|6wym|4t5s|2vfe|1hg2|o26|91q|2hd|eo|16|0|0$6760064|8|5a|lo|1zy|62y|g6s|1342|2ajq|47va|6n7e|8w30|9xz4|9c1a|75os|43dy|1j84|aia|ns$6761058|a|2m|a2|vq|2sq|7ce|i2v|15fi|2bq6|451q|6i2h|8qug|9xvy|9fro|7929|44n6|1i8a|9n8|ix$5770068|a|3o|ci|1ae|3xe|aic|p42|1iqg|2y5i|52z6|7ngs|a04y|b9m8|aymg|936c|6dbe|3qle|1ojs|ia0|2y0|78|8$577106c|1y|4s|ik|1ku|4hk|bjs|qp8|1jk6|2xbg|4zto|7k22|9xr4|bcn6|b1vc|94xi|6d64|3obg|1o0n|iv8|32o|60|1$6670068|14|4i|f4|1f0|4ac|bcq|qsc|1lvo|3608|5l7u|8olw|br5e|dt1s|dyd0|c0s8|8ra4|5bp8|2jgc|uiw|5oq|f4|a$6671068|14|4i|f4|1f0|4ac|bcq|qsc|1lvo|3608|5l7u|8olw|br5e|dt1s|dyd0|c0s8|8ra4|5bp8|2jgc|uiw|5oq|f4|a$8850054|o|3w|gi|1os|61i|iag|1d5y|39h0|6m5k|b9mc|g9wu|ioks|f0rg|73x0|1dd8$8851054|o|3w|gi|1os|61i|iag|1d5y|39h0|6m5k|b9mc|g9wu|ioks|f0rg|73x0|1dd8$4880042|0|g|14|4u|ho|1dq|3v8|a3i|o7s|1go4|2ux4|5274|83iw|bn3s|esmg|giem|g20o|djtg|9uvk|66hi|3bak|1iei|k04|5ai|s0|1k|0|0$488107g|2g|8o|vw|2x8|8f4|lcg|1d54|2t2g|53c0|89e8|bvwg|f0a8|gj28|fum8|da08|9r1k|68p4|3faw|1kf8|jyc|4pc|gg|0|0|0$6861058|a|2o|as|10g|3f0|9ik|oym|1ox4|3oq0|73yk|c6ji|i0nk|mmrg|nwho|km7i|dex8|5rxo|1b3c|3no$6860064|8|5i|og|2fe|7u4|m6s|1l6g|3lr6|76l8|cdoo|iakg|mpra|nrl0|kfqq|db74|5t68|1d0c|42e$7761058|8|2c|aw|zw|394|9nc|pb8|1qrw|3uw4|7l1k|d420|ju98|pdn4|rejs|obk8|gamg|7bi4|1rx8|5cw$7760064|o|5m|oo|2mm|7yk|mtu|1mxg|3r8g|7kkk|ddnk|k39s|pjqc|rbxs|o0po|g6rg|7dgw|1tpk|5y2$587106a|13|4k|ha|1nz|5b7|exp|11oe|2efc|4zc1|9c3w|fk7z|mrb4|t0oz|vyqx|u2f4|ny2y|fx3y|8ce4|33dh|nzr|285|27$587006a|13|4k|ha|1nz|5b7|exp|11oe|2efc|4zc1|9c3w|fk7z|mrb4|t0oz|vyqx|u2f4|ny2y|fx3y|8ce4|33dh|nzr|285|27$5781076|1w|as|vo|2x2|8qo|n4s|1jo4|3cvu|6nau|bt5g|ivl8|quyw|xlp6|10rs6|z6yc|tiek|llbi|dmoa|7bzq|385g|1124|728|k8|a|0$578006g|w|3i|e0|1d8|3so|a6u|pt8|1ne0|3hs4|6pro|bs5i|inco|qe26|x8z8|10te0|zlt4|tyf0|lpj2|dho0|74y8|34wg|1241|88y|uw|1m|1$6771068|13|4o|h1|1o1|5fl|fj6|13o1|2l9h|5kdo|auh5|iwi5|t0vr|130rq|19izn|19jhg|12ox1|rjyk|fphp|6inz|1o5s|75s|9f$6770068|13|4o|h1|1o1|5fl|fj6|13o1|2l9h|5kdo|auh5|iwi5|t0vr|130rq|19izn|19jhg|12ox1|rjyk|fphp|6inz|1o5s|75s|9f$668006c|14|3m|ew|1es|408|abk|qkw|1qo8|3p8g|79e0|d0g8|l8ww|v4rc|14kbk|1akko|1avg0|1520o|v2cs|k74o|b6ws|56c8|1ua4|fw0|218|3s|2$6681081s|80|vk|2x4|8o0|mzk|1l2o|3k3k|74ts|d32o|llog|vn40|14yio|1akwg|1ad60|14iu0|uw74|kcu8|bfcg|59y0|1tzk|ekg|1ew|14|0$7861058|8|2u|bq|14u|43y|c8c|y86|2heo|5vrk|cdti|ndnc|12gza|1i5ta|1sko8|1rlk4|1cayu|p4b4|7d6k|tfa$7860064|8|5q|rg|2ws|a00|u74|2bcy|5p12|ceky|nmgi|12zpc|1igo0|1sg4c|1r9zq|1c072|p4fw|7hr0|usu$588006g|w|3q|hw|1jg|4pm|df8|104y|2hb0|5m7e|bqy1|mf9s|134hc|1pts8|2fjb4|31rj4|3d96k|390b8|2prm0|1y704|16wmk|lsty|8jyk|2a92|c1c|ru|m$5881076|1o|8g|10o|3eg|ax4|v68|2990|5dda|bhrm|mf94|13izg|1qlko|2ge1k|325ik|3cljs|37y9i|2p6uc|1yba8|17cus|m36w|8l54|27ks|ae4|hq|6$6870068|12|50|is|1wi|6ne|k9u|1j8e|3up8|8utk|im4e|zaw6|1nh90|2gfrq|36w3s|3ko32|3ewew|2qu06|1sbei|v4yy|9rvo|1k2y|30u$6871068|12|50|is|1wi|6ne|k9u|1j8e|3up8|8utk|im4e|zaw6|1nh90|2gfrq|36w3s|3ko32|3ewew|2qu06|1sbei|v4yy|9rvo|1k2y|30u$8860064|8|5y|ug|3es|ce0|13gg|3788|8eb8|jlco|14aws|20g1k|32uuk|40bm0|4d0km|3ppdk|27w70|s4og|3zz8$8861058|8|2w|cg|19s|4u8|f6o|18y0|3g2o|8pzk|jnyo|1429k|1zmds|327hc|40cjc|4dh9c|3qc60|27zwo|rvv4|3wn4$7771068|1w|5k|mw|24w|75g|lm0|1m0c|41cc|9adc|jm9c|11on8|1sn34|2q9q8|3mklc|45plk|42enw|3cjk4|28pz0|14nic|di5k|2bgk|4qo$7770068|8|44|f0|1ps|69w|jfs|1ihc|3wk0|968w|jnra|11zo4|1t5bw|2qfrw|3mcys|458fs|4224y|3cq34|291d2|14obc|dens|2azk|54u$6781081s|88|zm|3hu|b78|w0y|2dnk|5t0a|crrs|pvpy|1bou2|2784c|39rrq|4b9z4|50i4q|54n6e|4l3g2|3jt8e|2clxw|1ap8u|k5qo|62qu|10ye|2iw|1k$678006c|10|3k|gs|1kw|4u2|dlo|1186|2mpi|63x0|d54l|q11g|1bctu|26ano|38lih|4ai3o|50ztq|55yn4|4m5e2|3jy1g|2c1sa|1a7na|k0jh|65lc|141q|3b2|36$7870068|11|56|kr|263|81x|q3w|23vr|5p14|e390|w41i|1uqnf|3gffr|5qgub|8dwgc|ank51|blzna|aq253|84dyy|4oyv2|1ubde|edp3|15sx$7871068|11|56|kr|263|81x|q3w|23vr|5p14|e390|w41i|1uqnf|3gffr|5qgub|8dwgc|ank51|blzna|aq253|84dyy|4oyv2|1ubde|edp3|15sx$6881081s|8k|13k|43k|dy4|165s|3c8g|8qa4|klts|18ydk|2hs4g|4ja4o|7g3d8|axoww|e92yw|gey2g|gl0q4|ejl04|axyhk|6wr6w|3h5v4|19q0g|aa7s|13do|1b8$688006c|10|3k|hs|1ru|5qo|h1c|1d9o|3pq0|98lk|lbuk|19hrs|2hpgs|4i2pk|7dw7w|avbhs|e8rwk|gh1rw|gnrf0|ekwg0|ax9c2|6vhn4|3gguc|19qzw|aj3c|16w0|1nm$7781081s|bc|148|46w|eew|17k0|3g9w|8z4w|li2w|1b9e0|2nu9g|4x4x0|88e4k|cc25k|gfp3c|jcvrk|k0ta0|i0b48|dwsck|91rsw|4pu2w|1svi8|fmmc|1ubs|2fk$778006c|w|3i|fs|1qg|5mk|gy6|1dis|3r5e|9hvw|m3tj|1c2t8|2o38q|4w9z8|86110|c9e7g|gee1c|jendo|k47wd|i29xw|dwk6y|9021k|4oq6d|1szk8|fxh6|1y88|339$8871068|10|5i|mo|2f4|9i8|wka|2ryw|7y8s|kv2o|1epfi|352gw|6btey|bf45w|iaa5k|plf2g|uvib0|vqabg|qynhg|hr0y8|84sbo|25pn4|86f8$8870068|10|5i|mo|2f4|9i8|wka|2ryw|7y8s|kv2o|1epfi|352gw|6btey|bf45w|iaa5k|plf2g|uvib0|vqabg|qynhg|hr0y8|84sbo|25pn4|86f8$7881081s|8s|17u|4qo|h5o|1j04|4mro|cyqe|wzaa|25xvc|4ps5c|9fo5c|h79p4|sc484|15r9i0|1iql2o|1razzk|1rvnkc|1jl5ja|14xgcg|ohbe4|b0po8|3abxw|irei|12im$788006c|w|3i|jo|1xu|6ok|l68|1shw|568y|dsfk|yd0l|27eh4|4qntc|9el8k|h3qzo|s68ms|15nm3c|1isc14|1rgzqk|1s1abg|1jlv86|14ur9c|oelf0|azx28|3ay2a|j7ts|1564$888006c|w|3i|ko|24w|7pk|pi0|2994|6ve8|jeog|1fdt6|3ibeo|82cpk|h6xq8|xt8i8|1on140|2q93kc|3yhh5s|531vr6|5puq3c|5k52hk|4lizrs|34fpf4|1mnz2g|l342w|4b6og|ceo6$8881081s|94|1c0|5fc|kmw|1x28|64pk|i71s|1d59c|3fkg0|7zrk0|h6yxs|xxibk|1oxt80|2qj540|3yj4cw|52su1s|5pgz20|5jza4w|4lmgjs|34mdtk|1mrjxs|l27nc|49syo|c3rk$";

struct TestCase {
    int n, m, k, p;
    bool operator<(const TestCase& o) const {
        if (n != o.n)
            return n < o.n;
        if (m != o.m)
            return m < o.m;
        if (k != o.k)
            return k < o.k;
        return p < o.p;
    }
    /* friend ostream& operator<<(ostream& os, const TestCase& tc) { */
    /*     return os << "(" << tc.n << ", " << tc.m << ", " << tc.k << ", " << tc.p << ")"; */
    /* } */
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // decompress precomp data
    map<TestCase, vector<long long>> TheMapa;
    for (int i = 0; i < (int)precomp.length(); i++) {
        TestCase tc;
        tc.n = precomp[i++] - '0';
        tc.m = precomp[i++] - '0';
        tc.k = precomp[i++] - '0';
        tc.p = precomp[i++] - '0';
        int fnz = precomp[i++] - '0';
        fnz = 10*fnz + precomp[i++] - '0';
        vector<long long> Vals;
        for (int it = 0; it < fnz; it++)
            Vals.push_back(0);
        while (true) {
            size_t chars_used;
            Vals.push_back(std::stoll(precomp.substr(i), &chars_used, 36));
            i += chars_used;
            if (precomp[i] == '$')
                break;
            i++;
        }
        while ((int)Vals.size() < 4*tc.k)
            Vals.push_back(0);
        TheMapa[tc] = Vals;
    }

    // test that
    /* for (auto it : TheMapa) { */
    /*     cerr << it.first << endl; */
    /*     cerr << deb::Container(it.second) << endl; */
    /* } */
    /*  */
    /* return 42; */

    // input
    int n, m;
    cin >> n >> m;
    vector<string>Pa(n);
    for (auto& row : Pa)
        cin >> row;
    vector<string>Pb(n);
    for (auto& row : Pb)
        cin >> row;

    // parity check
    int pa = 0, pb = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (Pa[i][j] == 'O')
                pa += i + j;
            if (Pb[i][j] == 'O')
                pb += i + j;
        }
    pa %= 2;
    pb %= 2;
    if (pa != pb) {
        cout << "0\n";
        return 0;
    }

    // target stats
    int k = 0, pm = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (Pb[i][j] == 'O') {
                k++;
                if (i > 0 && Pb[i-1][j] == '.')
                    pm++;
                if (i < n - 1 && Pb[i+1][j] == '.')
                    pm++;
                if (j > 0 && Pb[i][j-1] == '.')
                    pm++;
                if (j < m - 1 && Pb[i][j+1] == '.')
                    pm++;
            }

    TestCase tc {min(n, m), max(n, m), k, pb};
    auto TheWektor = TheMapa[tc];
    
    // compute the result
    long long X = 0;
    for (int i = 0; i <= 4*k; i++)
        X += i * TheWektor[i];
    cout << fixed << setprecision(15) << (double)pm / X << endl;

    return 0;
}