/*
TASK: hop
LANG: C++
*/

#include<iostream>
#include<algorithm>
using namespace std;
struct asd{
int k,i,j;
}mm[]={
{893, 0, 0},
{5, 3, 4},
{10, 6, 8},
{13, 5, 12},
{15, 9, 12},
{17, 8, 15},
{20, 12, 16},
{25, 7, 24},
{25, 15, 20},
{26, 10, 24},
{29, 20, 21},
{30, 18, 24},
{34, 16, 30},
{35, 21, 28},
{37, 12, 35},
{39, 15, 36},
{40, 24, 32},
{41, 9, 40},
{45, 27, 36},
{50, 14, 48},
{50, 30, 40},
{51, 24, 45},
{52, 20, 48},
{53, 28, 45},
{55, 33, 44},
{58, 40, 42},
{60, 36, 48},
{61, 11, 60},
{65, 39, 52},
{65, 33, 56},
{65, 25, 60},
{65, 16, 63},
{68, 32, 60},
{70, 42, 56},
{73, 48, 55},
{74, 24, 70},
{75, 45, 60},
{75, 21, 72},
{78, 30, 72},
{80, 48, 64},
{82, 18, 80},
{85, 13, 84},
{85, 36, 77},
{85, 40, 75},
{85, 51, 68},
{87, 60, 63},
{89, 39, 80},
{90, 54, 72},
{91, 35, 84},
{95, 57, 76},
{97, 65, 72},
{100, 28, 96},
{100, 60, 80},
{101, 20, 99},
{102, 48, 90},
{104, 40, 96},
{105, 63, 84},
{106, 56, 90},
{109, 60, 91},
{110, 66, 88},
{111, 36, 105},
{113, 15, 112},
{115, 69, 92},
{116, 80, 84},
{117, 45, 108},
{119, 56, 105},
{120, 72, 96},
{122, 22, 120},
{123, 27, 120},
{125, 44, 117},
{125, 75, 100},
{125, 35, 120},
{130, 50, 120},
{130, 78, 104},
{130, 66, 112},
{130, 32, 126},
{135, 81, 108},
{136, 64, 120},
{137, 88, 105},
{140, 84, 112},
{143, 55, 132},
{145, 100, 105},
{145, 24, 143},
{145, 17, 144},
{145, 87, 116},
{146, 96, 110},
{148, 48, 140},
{149, 51, 140},
{150, 90, 120},
{150, 42, 144},
{153, 72, 135},
{155, 93, 124},
{156, 60, 144},
{157, 85, 132},
{159, 84, 135},
{160, 96, 128},
{164, 36, 160},
{165, 99, 132},
{169, 119, 120},
{169, 65, 156},
{170, 26, 168},
{170, 80, 150},
{170, 72, 154},
{170, 102, 136},
{173, 52, 165},
{174, 120, 126},
{175, 49, 168},
{175, 105, 140},
{178, 78, 160},
{180, 108, 144},
{181, 19, 180},
{182, 70, 168},
{183, 33, 180},
{185, 60, 175},
{185, 57, 176},
{185, 111, 148},
{185, 104, 153},
{187, 88, 165},
{190, 114, 152},
{193, 95, 168},
{194, 130, 144},
{195, 75, 180},
{195, 48, 189},
{195, 99, 168},
{195, 117, 156},
{197, 28, 195},
{200, 56, 192},
{200, 120, 160},
{202, 40, 198},
{203, 140, 147},
{204, 96, 180},
{205, 84, 187},
{205, 123, 164},
{205, 133, 156},
{205, 45, 200},
{208, 80, 192},
{210, 126, 168},
{212, 112, 180},
{215, 129, 172},
{218, 120, 182},
{219, 144, 165},
{220, 132, 176},
{221, 140, 171},
{221, 21, 220},
{221, 104, 195},
{221, 85, 204},
{222, 72, 210},
{225, 63, 216},
{225, 135, 180},
{226, 30, 224},
{229, 60, 221},
{230, 138, 184},
{232, 160, 168},
{233, 105, 208},
{234, 90, 216},
{235, 141, 188},
{238, 112, 210},
{240, 144, 192},
{241, 120, 209},
{244, 44, 240},
{245, 147, 196},
{246, 54, 240},
{247, 95, 228},
{250, 70, 240},
{250, 88, 234},
{250, 150, 200},
{255, 39, 252},
{255, 120, 225},
{255, 153, 204},
{255, 108, 231},
{257, 32, 255},
{259, 84, 245},
{260, 100, 240},
{260, 132, 224},
{260, 64, 252},
{260, 156, 208},
{261, 180, 189},
{265, 96, 247},
{265, 23, 264},
{265, 140, 225},
{265, 159, 212},
{267, 117, 240},
{269, 69, 260},
{270, 162, 216},
{272, 128, 240},
{273, 105, 252},
{274, 176, 210},
{275, 165, 220},
{275, 77, 264},
{277, 115, 252},
{280, 168, 224},
{281, 160, 231},
{285, 171, 228},
{286, 110, 264},
{287, 63, 280},
{289, 161, 240},
{289, 136, 255},
{290, 34, 288},
{290, 174, 232},
{290, 48, 286},
{291, 195, 216},
{292, 192, 220},
{293, 68, 285},
{295, 177, 236},
{296, 96, 280},
{298, 102, 280},
{299, 115, 276},
{300, 180, 240},
{300, 84, 288},
{303, 60, 297},
{305, 183, 244},
{305, 55, 300},
{305, 136, 273},
{306, 144, 270},
{310, 186, 248},
{312, 120, 288},
{313, 25, 312},
{314, 170, 264},
{315, 189, 252},
{317, 75, 308},
{318, 168, 270},
{320, 192, 256},
{323, 152, 285},
{325, 125, 300},
{325, 36, 323},
{325, 80, 315},
{325, 91, 312},
{325, 165, 280},
{327, 180, 273},
{328, 72, 320},
{333, 108, 315},
{337, 175, 288},
{338, 130, 312},
{339, 45, 336},
{340, 144, 308},
{340, 52, 336},
{340, 160, 300},
{346, 104, 330},
{349, 180, 299},
{350, 98, 336},
{351, 135, 324},
{356, 156, 320},
{357, 168, 315},
{362, 38, 360},
{364, 140, 336},
{365, 76, 357},
{365, 27, 364},
{366, 66, 360},
{369, 81, 360},
{370, 114, 352},
{370, 120, 350},
{374, 176, 330},
{375, 132, 351},
{375, 105, 360},
{377, 145, 348},
{377, 135, 352},
{377, 152, 345},
{386, 190, 336},
{389, 189, 340},
{390, 150, 360},
{390, 96, 378},
{391, 184, 345},
{394, 56, 390},
{400, 112, 384},
{401, 40, 399},
{403, 155, 372},
{404, 80, 396},
{407, 132, 385},
{408, 192, 360},
{409, 120, 391},
{410, 90, 400},
{410, 168, 374},
{416, 160, 384},
{421, 29, 420},
{425, 119, 408},
{425, 87, 416},
{425, 65, 420},
{425, 180, 385},
{427, 77, 420},
{429, 165, 396},
{433, 145, 408},
{435, 51, 432},
{435, 72, 429},
{442, 170, 408},
{442, 42, 440},
{444, 144, 420},
{445, 84, 437},
{447, 153, 420},
{450, 126, 432},
{451, 99, 440},
{452, 60, 448},
{455, 112, 441},
{455, 175, 420},
{457, 168, 425},
{458, 120, 442},
{468, 180, 432},
{475, 133, 456},
{481, 156, 455},
{481, 31, 480},
{481, 185, 444},
{485, 93, 476},
{485, 44, 483},
{488, 88, 480},
{492, 108, 480},
{493, 132, 475},
{493, 155, 468},
{494, 190, 456},
{500, 140, 480},
{500, 176, 468},
{505, 100, 495},
{510, 78, 504},
{514, 64, 510},
{518, 168, 490},
{519, 156, 495},
{520, 128, 504},
{525, 147, 504},
{530, 46, 528},
{530, 192, 494},
{533, 92, 525},
{533, 117, 520},
{538, 138, 520},
{543, 57, 540},
{545, 33, 544},
{545, 184, 513},
{549, 99, 540},
{550, 154, 528},
{555, 171, 528},
{555, 180, 525},
{557, 165, 532},
{565, 75, 560},
{574, 126, 560},
{575, 161, 552},
{577, 48, 575},
{580, 68, 576},
{580, 96, 572},
{585, 144, 567},
{586, 136, 570},
{591, 84, 585},
{592, 192, 560},
{595, 91, 588},
{600, 168, 576},
{606, 120, 594},
{610, 110, 600},
{613, 35, 612},
{615, 135, 600},
{617, 105, 608},
{625, 175, 600},
{626, 50, 624},
{629, 100, 621},
{634, 150, 616},
{650, 72, 646},
{650, 160, 630},
{650, 182, 624},
{656, 144, 640},
{663, 63, 660},
{671, 121, 660},
{675, 189, 648},
{676, 476, 480},
{677, 52, 675},
{678, 90, 672},
{680, 104, 672},
{685, 156, 667},
{685, 37, 684},
{687, 180, 663},
{689, 111, 680},
{696, 480, 504},
{697, 153, 680},
{697, 185, 672},
{707, 140, 693},
{715, 176, 693},
{724, 76, 720},
{725, 120, 715},
{725, 500, 525},
{725, 85, 720},
{730, 480, 550},
{730, 54, 728},
{730, 152, 714},
{732, 132, 720},
{733, 108, 725},
{738, 162, 720},
{746, 504, 550},
{754, 520, 546},
{761, 39, 760},
{765, 117, 756},
{769, 481, 600},
{771, 96, 765},
{776, 520, 576},
{779, 171, 760},
{780, 192, 756},
{783, 540, 567},
{785, 56, 783},
{788, 112, 780},
{790, 474, 632},
{791, 105, 784},
{793, 168, 775},
{793, 143, 780},
{795, 477, 636},
{795, 69, 792},
{797, 555, 572},
{800, 480, 640},
{802, 80, 798},
{803, 528, 605},
{805, 483, 644},
{808, 160, 792},
{810, 486, 648},
{812, 560, 588},
{815, 489, 652},
{820, 492, 656},
{820, 180, 800},
{820, 532, 624},
{822, 528, 630},
{825, 495, 660},
{829, 540, 629},
{830, 498, 664},
{835, 501, 668},
{840, 504, 672},
{841, 41, 840},
{841, 580, 609},
{842, 58, 840},
{843, 480, 693},
{845, 123, 836},
{845, 595, 600},
{845, 507, 676},
{845, 116, 837},
{850, 510, 680},
{850, 174, 832},
{850, 130, 840},
{850, 594, 608},
{854, 154, 840},
{855, 513, 684},
{860, 516, 688},
{861, 189, 840},
{865, 504, 703},
{865, 519, 692},
{867, 483, 720},
{870, 600, 630},
{870, 102, 864},
{870, 144, 858},
{870, 522, 696},
{872, 480, 728},
{873, 585, 648},
{875, 525, 700},
{876, 576, 660},
{880, 528, 704},
{884, 560, 684},
{884, 84, 880},
{885, 531, 708},
{890, 534, 712},
{890, 168, 874},
{895, 537, 716},
{898, 560, 702},
{899, 620, 651},
{900, 540, 720},
{901, 60, 899},
{901, 476, 765},
{904, 120, 896},
{905, 95, 900},
{905, 616, 663},
{905, 543, 724},
{909, 180, 891},
{910, 546, 728},
{915, 549, 732},
{915, 165, 900},
{915, 621, 672},
{920, 552, 736},
{922, 522, 760},
{925, 43, 924},
{925, 533, 756},
{925, 555, 740},
{925, 520, 765},
{928, 640, 672},
{929, 129, 920},
{930, 558, 744},
{935, 143, 924},
{935, 561, 748},
{939, 75, 936},
{940, 564, 752},
{941, 580, 741},
{942, 510, 792},
{945, 567, 756},
{949, 624, 715},
{950, 570, 760},
{953, 615, 728},
{954, 504, 810},
{955, 573, 764},
{957, 660, 693},
{959, 616, 735},
{960, 576, 768},
{962, 638, 720},
{962, 62, 960},
{964, 480, 836},
{965, 124, 957},
{965, 579, 772},
{965, 475, 840},
{970, 186, 952},
{970, 88, 966},
{970, 650, 720},
{970, 582, 776},
{975, 585, 780},
{975, 495, 840},
{975, 108, 969},
{975, 612, 759},
{976, 176, 960},
{980, 588, 784},
{981, 540, 819},
{985, 591, 788},
{985, 696, 697},
{985, 473, 864},
{985, 140, 975},
{986, 680, 714},
{990, 594, 792},
{995, 597, 796},
{1000, 600, 800},
{1003, 195, 885},
{1005, 603, 804},
{1007, 532, 855},
{1009, 559, 840},
{1010, 606, 808},
{1010, 672, 754},
{1011, 525, 864},
{1013, 45, 1012},
{1014, 714, 720},
{1015, 168, 1001},
{1015, 119, 1008},
{1015, 700, 735},
{1015, 609, 812},
{1017, 135, 1008},
{1020, 156, 1008},
{1020, 480, 900},
{1020, 612, 816},
{1021, 660, 779},
{1022, 672, 770},
{1025, 496, 897},
{1025, 64, 1023},
{1025, 615, 820},
{1025, 665, 780},
{1028, 128, 1020},
{1030, 618, 824},
{1033, 192, 1015},
{1035, 621, 828},
{1037, 488, 915},
{1037, 645, 812},
{1037, 187, 1020},
{1040, 528, 896},
{1040, 624, 832},
{1042, 558, 880},
{1044, 720, 756},
{1045, 627, 836},
{1047, 540, 897},
{1050, 630, 840},
{1054, 496, 930},
{1055, 633, 844},
{1059, 675, 816},
{1060, 560, 900},
{1060, 92, 1056},
{1060, 636, 848},
{1061, 620, 861},
{1065, 639, 852},
{1066, 184, 1050},
{1066, 616, 870},
{1067, 715, 792},
{1069, 731, 780},
{1070, 642, 856},
{1071, 504, 945},
{1073, 495, 952},
{1073, 740, 777},
{1075, 645, 860},
{1080, 648, 864},
{1082, 682, 840},
{1085, 651, 868},
{1086, 114, 1080},
{1088, 512, 960},
{1090, 600, 910},
{1090, 654, 872},
{1090, 66, 1088},
{1093, 132, 1085},
{1095, 657, 876},
{1095, 720, 825},
{1095, 81, 1092},
{1096, 704, 840},
{1097, 585, 928},
{1099, 595, 924},
{1100, 660, 880},
{1102, 760, 798},
{1105, 663, 884},
{1105, 561, 952},
{1105, 744, 817},
{1105, 105, 1100},
{1105, 520, 975},
{1105, 169, 1092},
{1105, 576, 943},
{1105, 47, 1104},
{1105, 700, 855},
{1109, 141, 1100},
{1110, 624, 918},
{1110, 666, 888},
{1113, 588, 945},
{1115, 669, 892},
{1119, 756, 825},
{1120, 672, 896},
{1122, 528, 990},
{1124, 640, 924},
{1125, 675, 900},
{1130, 552, 986},
{1130, 678, 904},
{1130, 792, 806},
{1130, 150, 1120},
{1131, 780, 819},
{1135, 681, 908},
{1139, 536, 1005},
{1140, 684, 912},
{1145, 687, 916},
{1145, 704, 903},
{1150, 690, 920},
{1153, 528, 1025},
{1154, 96, 1150},
{1155, 693, 924},
{1156, 544, 1020},
{1156, 644, 960},
{1157, 68, 1155},
{1157, 507, 1040},
{1157, 765, 868},
{1158, 570, 1008},
{1160, 136, 1152},
{1160, 800, 840},
{1160, 192, 1144},
{1160, 696, 928},
{1164, 780, 864},
{1165, 517, 1044},
{1165, 525, 1040},
{1165, 699, 932},
{1166, 616, 990},
{1167, 567, 1020},
{1168, 768, 880},
{1170, 594, 1008},
{1170, 702, 936},
{1173, 552, 1035},
{1175, 705, 940},
{1180, 708, 944},
{1182, 168, 1170},
{1183, 833, 840},
{1185, 711, 948},
{1186, 736, 930},
{1189, 820, 861},
{1189, 611, 1020},
{1189, 660, 989},
{1190, 714, 952},
{1190, 560, 1050},
{1190, 504, 1078},
{1190, 182, 1176},
{1191, 684, 975},
{1193, 832, 855},
{1195, 717, 956},
{1199, 660, 1001},
{1200, 720, 960},
{1201, 49, 1200},
{1202, 480, 1102},
{1203, 120, 1197},
{1205, 476, 1107},
{1205, 147, 1196},
{1205, 600, 1045},
{1205, 723, 964},
{1207, 568, 1065},
{1210, 726, 968},
{1215, 729, 972},
{1217, 705, 992},
{1218, 840, 882},
{1219, 644, 1035},
{1220, 544, 1092},
{1220, 828, 896},
{1220, 732, 976},
{1224, 576, 1080},
{1225, 735, 980},
{1226, 70, 1224},
{1229, 140, 1221},
{1230, 738, 984},
{1230, 504, 1122},
{1230, 798, 936},
{1233, 792, 945},
{1235, 627, 1064},
{1235, 475, 1140},
{1235, 741, 988},
{1237, 612, 1075},
{1240, 744, 992},
{1241, 816, 935},
{1241, 584, 1095},
{1243, 165, 1232},
{1245, 747, 996},
{1246, 546, 1120},
{1247, 860, 903},
{1248, 480, 1152},
{1249, 799, 960},
{1250, 750, 1000},
{1250, 672, 1054},
{1252, 100, 1248},
{1255, 753, 1004},
{1256, 680, 1056},
{1258, 592, 1110},
{1258, 858, 920},
{1260, 756, 1008},
{1261, 485, 1164},
{1261, 539, 1140},
{1261, 845, 936},
{1263, 87, 1260},
{1265, 759, 1012},
{1267, 133, 1260},
{1270, 762, 1016},
{1272, 672, 1080},
{1274, 490, 1176},
{1275, 600, 1125},
{1275, 765, 1020},
{1275, 891, 912},
{1275, 540, 1155},
{1276, 880, 924},
{1277, 748, 1035},
{1280, 768, 1024},
{1285, 893, 924},
{1285, 160, 1275},
{1285, 637, 1116},
{1285, 771, 1028},
{1287, 495, 1188},
{1289, 560, 1161},
{1290, 774, 1032},
{1292, 608, 1140},
{1295, 728, 1071},
{1295, 777, 1036},
{1297, 72, 1295},
{1300, 144, 1292},
{1300, 660, 1120},
{1300, 500, 1200},
{1300, 816, 1012},
{1300, 780, 1040},
{1301, 51, 1300},
{1305, 900, 945},
{1305, 153, 1296},
{1305, 783, 1044},
{1306, 630, 1144},
{1308, 720, 1092},
{1309, 616, 1155},
{1310, 786, 1048},
{1313, 735, 1088},
{1313, 505, 1212},
{1314, 864, 990},
{1315, 789, 1052},
{1320, 792, 1056},
{1322, 600, 1178},
{1325, 884, 987},
{1325, 115, 1320},
{1325, 795, 1060},
{1325, 480, 1235},
{1325, 700, 1125},
{1326, 624, 1170},
{1326, 840, 1026},
{1326, 510, 1224},
{1326, 126, 1320},
{1330, 798, 1064},
{1334, 920, 966},
{1335, 609, 1188},
{1335, 585, 1200},
{1335, 801, 1068},
{1339, 515, 1236},
{1340, 804, 1072},
{1343, 632, 1185},
{1345, 807, 1076},
{1345, 833, 1056},
{1345, 504, 1247},
{1346, 770, 1104},
{1347, 840, 1053},
{1348, 700, 1152},
{1350, 810, 1080},
{1351, 665, 1176},
{1352, 520, 1248},
{1352, 952, 960},
{1354, 104, 1350},
{1355, 813, 1084},
{1356, 180, 1344},
{1358, 910, 1008},
{1360, 816, 1088},
{1360, 576, 1232},
{1360, 640, 1200},
{1361, 561, 1240},
{1363, 940, 987},
{1365, 819, 1092},
{1365, 693, 1176},
{1365, 525, 1260},
{1369, 840, 1081},
{1370, 822, 1096},
{1370, 880, 1050},
{1370, 74, 1368},
{1371, 504, 1275},
{1373, 148, 1365},
{1375, 484, 1287},
{1375, 825, 1100},
{1377, 648, 1215},
{1378, 800, 1122},
{1378, 728, 1170},
{1378, 530, 1272},
{1380, 828, 1104},
{1381, 931, 1020},
{1383, 783, 1140},
{1385, 575, 1260},
{1385, 831, 1108},
{1385, 663, 1216},
{1387, 912, 1045},
{1390, 834, 1112},
{1391, 535, 1284},
{1392, 960, 1008},
{1394, 656, 1230},
{1394, 910, 1056},
{1395, 837, 1116},
{1396, 720, 1196},
{1398, 630, 1248},
{1400, 840, 1120},
{1402, 520, 1302},
{1404, 540, 1296},
{1405, 53, 1404},
{1405, 800, 1155},
{1405, 843, 1124},
{1409, 159, 1400},
{1410, 846, 1128},
{1411, 664, 1245},
{1412, 900, 1088},
{1413, 765, 1188},
{1415, 849, 1132},
{1417, 780, 1183},
{1417, 545, 1308},
{1417, 792, 1175},
{1418, 518, 1320},
{1420, 852, 1136},
{1421, 980, 1029},
{1424, 624, 1280},
{1425, 855, 1140},
{1428, 672, 1260},
{1430, 858, 1144},
{1430, 550, 1320},
{1430, 726, 1232},
{1431, 756, 1215},
{1433, 592, 1305},
{1435, 931, 1092},
{1435, 588, 1309},
{1435, 861, 1148},
{1440, 864, 1152},
{1443, 555, 1332},
{1443, 93, 1440},
{1443, 957, 1080},
{1445, 477, 1364},
{1445, 867, 1156},
{1445, 612, 1309},
{1445, 680, 1275},
{1445, 76, 1443},
{1445, 805, 1200},
{1446, 720, 1254},
{1448, 152, 1440},
{1450, 870, 1160},
{1450, 170, 1440},
{1450, 1000, 1050},
{1450, 728, 1254},
{1450, 666, 1288},
{1455, 132, 1449},
{1455, 873, 1164},
{1455, 975, 1080},
{1456, 560, 1344},
{1460, 876, 1168},
{1460, 960, 1100},
{1460, 108, 1456},
{1462, 688, 1290},
{1465, 879, 1172},
{1465, 583, 1344},
{1465, 936, 1127},
{1469, 565, 1356},
{1469, 740, 1269},
{1470, 882, 1176},
{1475, 885, 1180},
{1479, 1020, 1071},
{1479, 696, 1305},
{1480, 888, 1184},
{1480, 480, 1400},
{1480, 832, 1224},
{1481, 969, 1120},
{1482, 570, 1368},
{1484, 784, 1260},
{1485, 891, 1188},
{1489, 689, 1320},
{1490, 510, 1400},
{1490, 814, 1248},
{1490, 894, 1192},
{1492, 1008, 1100},
{1493, 532, 1395},
{1495, 575, 1380},
{1495, 759, 1288},
{1495, 897, 1196},
{1496, 704, 1320},
{1500, 900, 1200},
{1500, 528, 1404},
};




int i,j,n,m;
#define maxn 1501
struct pp{int x,y;}q1[maxn*maxn],q2[maxn*maxn],n1,n2;
bool u1[maxn][maxn],u2[maxn][maxn];
int s1,s2;
asd h1[200],h2[200];
int brh1,brh2;
int d1[maxn][maxn],d2[maxn][maxn];
void init(){  //freopen("inp1.txt","rt",stdin);
	cin>>n>>m;
    cin>>n1.x>>n1.y>>s1;
    cin>>n2.x>>n2.y>>s2;
    //male
    h1[++brh1].i=s1;h1[brh1].j=0;
    h1[++brh1].i=-s1;h1[brh1].j=0;
    h1[++brh1].i=0;h1[brh1].j=s1;
    h1[++brh1].i=0;h1[brh1].j=-s1;

    for(i=1;i<=mm[0].k;i++)
    	if(mm[i].k==s1){
        	h1[++brh1].i=mm[i].i;h1[brh1].j=mm[i].j;
            h1[++brh1].i=-mm[i].i;h1[brh1].j=mm[i].j;
            h1[++brh1].i=-mm[i].i;h1[brh1].j=-mm[i].j;
            h1[++brh1].i=mm[i].i;h1[brh1].j=-mm[i].j;
	h1[++brh1].j=mm[i].i;h1[brh1].i=mm[i].j;
            h1[++brh1].j=-mm[i].i;h1[brh1].i=mm[i].j;
            h1[++brh1].j=-mm[i].i;h1[brh1].i=-mm[i].j;
            h1[++brh1].j=mm[i].i;h1[brh1].i=-mm[i].j;
        }
   //female
   h2[++brh2].i=s2;h2[brh2].j=0;
    h2[++brh2].i=-s2;h2[brh2].j=0;
    h2[++brh2].i=0;h2[brh2].j=s2;
    h2[++brh2].i=0;h2[brh2].j=-s2;

    for(i=1;i<=mm[0].k;i++)
    	if(mm[i].k==s2){
        	h2[++brh2].i=mm[i].i;h2[brh2].j=mm[i].j;
            h2[++brh2].i=-mm[i].i;h2[brh2].j=mm[i].j;
            h2[++brh2].i=-mm[i].i;h2[brh2].j=-mm[i].j;
            h2[++brh2].i=mm[i].i;h2[brh2].j=-mm[i].j;
	h2[++brh2].j=mm[i].i;h2[brh2].i=mm[i].j;
            h2[++brh2].j=-mm[i].i;h2[brh2].i=mm[i].j;
            h2[++brh2].j=-mm[i].i;h2[brh2].i=-mm[i].j;
            h2[++brh2].j=mm[i].i;h2[brh2].i=-mm[i].j;
        }
        
}
void solve();
void bfs1();
void bfs2();
//#include<time.h>
//clock_t beg;
int main(){//beg=clock();
	init();
    solve();
    return 0;
}
int br1,br2;
bool check1(int x,int y){
	if(x<0 || x>n || y<0 || y>m || u1[x][y])return 0;
    return 1;
}
bool check2(int x,int y){
	if(x<0 || x>n || y<0 || y>m || u2[x][y])return 0;
    return 1;
}
void solve(){
	bfs1();
	bfs2();
int best=999999;
for(i=0;i<=n;i++)
	for(j=0;j<=m;j++)
		if(u1[i][j] && u2[i][j])best=min(best,d1[i][j]+d2[i][j]);
if(best==999999)cout<<0<<endl;
else cout<<best<<endl;
//cout<<double(clock()-beg)/CLOCKS_PER_SEC<<endl;
	
//for(i=1;i<=brh1;i++)cout<<h1[i].i<<" "<<h1[i].j<<endl;
}

void bfs1(){
	br1=0;
	u1[n1.x][n1.y]=1;
    q1[++br1]=n1;
    int temp=1;
    while(temp<=br1){
        for(i=1;i<=brh1;i++)
        	if(br1<500000 && check1(q1[temp].x+h1[i].i,q1[temp].y+h1[i].j)){
                q1[++br1].x=q1[temp].x+h1[i].i;
                q1[br1].y=q1[temp].y+h1[i].j;
                u1[q1[br1].x][q1[br1].y]=1;
		d1[q1[br1].x][q1[br1].y]=d1[q1[temp].x][q1[temp].y]+1;
            }
        temp++;
    }
    //for(i=1;i<=br1;i++)cout<<q1[i].x<<" "<<q1[i].y<<endl;
}

void bfs2(){
	br2=0;
	u2[n2.x][n2.y]=1;
    q2[++br2]=n2;
    int temp=1;
    while(temp<=br2){
        for(i=1;i<=brh2;i++)
        	if(br2<500000 && check2(q2[temp].x+h2[i].i,q2[temp].y+h2[i].j)){
                q2[++br2].x=q2[temp].x+h2[i].i;
                q2[br2].y=q2[temp].y+h2[i].j;
                u2[q2[br2].x][q2[br2].y]=1;
		d2[q2[br2].x][q2[br2].y]=d2[q2[temp].x][q2[temp].y]+1;
            }
        temp++;
    }
    //for(i=1;i<=br2;i++)cout<<q2[i].x<<" "<<q2[i].y<<endl;
}
