Input: 1584 1583 1 1584
479 1574
105 786
594 848
327 1328
10 1037
460 1456
161 878
395 1485
156 225
41 1235
184 362
185 821
12 1554
425 1354
224 1197
446 1098
657 1509
173 290
240 1471
218 1426
145 1147
141 261
113 1536
8 1170
275 1499
364 754
378 462
987 1033
854 1548
21 1169
419 1198
77 751
90 816
653 1384
710 956
809 959
947 1164
848 1510
265 1555
778 949
594 1392
726 1578
840 1059
525 1515
1055 1487
11 1311
566 610
34 1343
316 1037
752 943
236 1005
29 1072
70 987
397 1419
316 1228
151 738
861 1218
1204 1218
764 856
1058 1184
407 1331
597 1038
213 1036
168 449
176 627
941 1204
238 667
1498 1543
43 1279
206 244
37 530
498 1580
608 1452
403 1364
583 852
46 442
621 1565
6 1572
459 630
701 729
757 1055
116 540
452 1583
1011 1536
305 822
1026 1174
912 1546
202 1518
525 1316
147 271
347 1420
473 549
587 974
987 1108
1456 1571
137 1319
681 1231
453 664
304 1249
560 794
891 1045
55 1121
1016 1504
341 777
605 812
666 917
639 988
658 1251
470 876
22 494
194 1324
51 171
692 736
432 557
51 344
12 845
64 1546
815 1084
266 372
304 963
638 1321
51 1196
565 838
91 645
715 1368
1339 1434
799 1078
1068 1289
949 980
415 950
11 138
416 1519
700 1412
439 553
764 1439
257 1358
20 772
300 898
36 943
116 312
192 279
388 1025
1168 1422
90 1567
84 196
1191 1474
1210 1407
125 1148
124 1023
109 276
644 714
248 550
476 991
134 998
292 1045
712 1178
765 1283
26 367
316 1472
735 1460
1089 1139
144 966
765 1281
274 435
282 1123
707 1548
415 508
424 1552
897 1490
318 449
420 875
495 1254
406 1553
175 623
437 782
867 1063
18 988
261 486
347 1103
470 854
392 810
556 1268
854 1360
304 1055
1441 1472
653 817
332 602
802 929
1031 1203
78 916
101 121
6 1055
100 1345
1089 1357
581 929
477 1009
23 890
224 990
1536 1547
535 1198
201 976
480 492
514 731
550 798
185 700
1097 1274
378 818
373 775
348 600
507 1154
377 913
389 729
217 869
152 1176
200 1183
224 1495
226 634
378 1339
865 980
1356 1490
212 263
262 1077
533 983
73 549
542 734
321 1343
110 940
742 888
269 714
986 1264
679 1399
919 1499
205 349
1114 1379
165 1398
537 754
420 1071
319 1525
51 81
1089 1245
636 1045
629 981
97 789
517 734
373 686
230 638
328 1230
290 1426
546 631
221 693
47 1173
519 533
219 334
1127 1468
732 1206
532 958
1375 1537
478 1427
540 1061
1285 1535
280 1039
229 332
725 1238
241 558
564 1113
628 1086
1467 1515
655 708
502 1223
791 1355
489 1169
94 581
756 1067
1206 1402
710 1040
750 1541
261 1104
545 718
760 1347
1003 1440
499 1289
288 1074
488 1514
847 1239
827 1190
485 1103
925 1048
106 1559
232 238
1136 1499
1008 1481
452 1124
395 1475
203 1331
422 1423
1245 1250
408 491
964 1022
837 1179
1232 1415
819 1557
503 564
210 357
517 781
246 976
174 558
1287 1407
274 403
181 376
446 1066
375 402
893 1205
615 680
52 427
541 1556
13 1045
198 929
245 1309
237 1395
1259 1417
431 721
879 1006
357 361
966 1365
160 662
315 752
100 737
712 781
728 1095
1029 1108
92 609
663 861
368 479
1010 1584
774 1502
332 688
648 1370
1365 1442
1105 1205
619 1302
369 979
99 458
496 596
283 1395
501 953
371 780
311 1181
1500 1543
294 1165
696 769
12 771
549 1160
198 511
267 1288
513 705
385 889
276 1518
305 1089
1292 1301
536 1003
982 1560
408 1087
900 1191
763 1387
170 1439
553 1007
331 929
282 761
1049 1575
634 791
32 1349
247 1091
701 730
716 1033
702 828
642 706
482 1188
239 1331
544 1473
1292 1309
1218 1341
643 1311
284 957
12 779
1027 1543
57 147
749 1292
896 1418
83 1155
217 1083
55 114
3 292
1200 1536
299 801
70 1270
83 559
650 1086
127 1152
657 1265
1249 1542
1052 1544
620 696
278 1488
194 1431
939 1496
185 1406
1272 1483
762 1469
951 1101
408 1089
357 776
952 1361
460 1234
657 727
1266 1577
72 745
306 669
884 1275
4 680
1172 1256
398 708
583 900
176 1089
899 998
178 590
1074 1376
160 1378
1169 1203
601 763
978 1157
936 1569
461 892
305 985
45 1193
651 1464
86 355
499 1303
196 444
1012 1266
1375 1538
460 1016
317 1167
330 958
147 281
406 1504
994 1057
569 1332
1207 1498
576 1341
534 773
326 625
35 1348
215 1135
881 1150
55 430
439 712
17 1476
19 1498
911 1260
794 1374
724 854
572 973
102 127
286 723
162 605
488 741
287 741
27 1004
100 602
714 1557
207 814
1392 1465
453 1341
900 915
447 811
49 1234
595 1058
392 1494
354 1579
370 585
514 1290
1461 1508
24 1398
39 592
488 1030
723 754
304 1099
315 358
149 777
44 897
486 970
499 533
834 1108
680 1352
568 879
98 1283
1269 1302
1112 1119
324 1016
82 954
104 967
178 1486
7 1292
470 1227
2 87
413 885
631 1299
1068 1221
205 1458
335 1360
912 1111
267 1076
729 1515
273 1542
143 1584
127 436
66 670
312 1382
684 900
1107 1410
954 1515
485 813
9 745
87 784
695 952
42 1231
258 1285
502 1242
192 417
830 1345
711 1492
127 414
1205 1504
46 1336
754 796
750 918
289 668
408 862
888 1226
266 1262
706 1467
663 792
194 285
198 308
183 1494
305 840
324 672
911 1545
401 1170
687 1367
276 642
971 1234
77 490
193 1253
785 1119
740 838
354 1308
85 784
702 1329
634 649
1085 1233
732 906
73 661
415 1231
288 694
24 1350
56 1392
49 1192
246 397
375 596
1443 1580
342 357
852 1499
154 1452
1027 1455
265 563
198 728
130 485
653 1472
384 405
140 1346
829 1115
777 1302
1021 1272
1281 1397
757 1003
92 323
127 1357
963 1347
164 362
1340 1389
155 735
521 608
417 553
505 1237
124 483
867 974
21 1014
465 727
790 937
367 1101
648 1278
689 1416
1227 1272
138 276
524 1200
26 1404
403 854
993 1231
62 178
1046 1137
810 1284
337 663
335 1034
319 1124
377 940
687 1281
1104 1125
253 1237
167 1114
765 1045
667 1143
2 840
370 718
412 1150
658 928
176 582
156 1245
754 1281
274 835
409 1382
577 1009
29 662
850 1366
83 1203
428 1193
267 724
19 141
365 378
91 765
315 354
697 1101
376 1466
1362 1525
187 977
120 623
544 1088
86 1391
119 923
531 1396
40 592
917 1428
759 1007
562 1052
578 1126
586 1228
487 509
657 758
907 926
170 750
279 1001
818 868
63 1350
382 517
899 1088
883 1233
75 1453
308 1220
859 1499
504 1061
472 1165
192 852
675 1303
353 1553
1071 1392
634 882
679 1520
927 1202
1075 1185
283 739
354 1393
82 703
1194 1417
1380 1568
319 965
1107 1195
9 1555
124 442
177 682
464 1430
595 1451
25 1306
460 1570
772 1497
339 799
474 539
126 1140
848 1544
502 864
408 1133
209 795
90 338
336 687
1127 1346
1386 1394
761 1518
242 335
624 1476
206 854
538 1227
123 1100
65 1205
185 343
341 1259
1444 1558
183 268
640 657
505 716
256 692
794 911
670 1043
284 648
1149 1160
429 915
348 942
223 986
940 1358
328 886
945 1190
503 1080
968 1089
121 897
128 1440
374 501
1144 1544
1337 1357
549 949
88 1062
124 1275
1131 1422
1202 1544
720 768
786 1064
81 647
584 1426
9 30
983 1117
854 984
634 1141
93 118
1334 1561
293 555
617 787
436 510
722 757
574 999
21 745
539 1557
1094 1396
114 717
1013 1407
263 1224
1034 1319
885 947
148 1009
334 386
352 823
1315 1518
345 783
156 646
662 814
1070 1499
475 572
169 1408
1095 1482
76 1072
848 976
415 932
393 1033
333 427
868 1581
303 413
396 499
1323 1565
983 1229
964 1072
924 1278
533 1566
14 432
653 1405
385 777
633 839
744 1317
334 940
989 1050
552 1067
5 1563
1331 1332
127 1199
1128 1256
279 704
314 1124
216 1082
595 1568
177 1383
363 618
857 1478
466 692
390 1208
463 1499
1283 1506
544 1002
190 625
167 363
1004 1283
463 1480
711 981
625 894
650 1493
281 312
383 1419
533 1226
1148 1520
103 890
1139 1413
471 782
1314 1533
411 1173
488 525
797 1424
1018 1057
938 1546
272 1022
433 1413
175 1089
912 1065
562 1318
238 359
624 926
952 1276
206 550
1476 1564
393 1198
926 1532
108 116
779 1169
1 176
791 1223
648 1185
733 1560
1157 1499
1050 1128
108 1148
95 182
531 1528
422 745
721 1304
166 823
1233 1499
484 667
457 962
40 1344
1360 1365
947 1258
289 1538
399 659
470 700
1361 1509
824 1022
419 676
995 1088
77 275
241 773
639 1074
113 1277
329 531
836 869
912 1252
445 1056
9 780
376 1400
511 1083
29 106
1186 1289
283 948
795 1158
791 1261
141 815
269 556
324 887
75 1427
1146 1451
531 794
1230 1539
52 546
158 865
806 1413
863 1423
89 743
752 803
59 909
617 1263
80 423
331 1305
518 1483
326 702
854 959
740 1205
895 1308
93 1189
699 1251
49 808
200 1255
1134 1402
302 673
354 689
130 713
968 1073
67 1349
424 876
257 746
247 1472
443 930
255 868
598 1517
558 1067
1310 1529
733 1030
58 230
62 1137
469 1557
1190 1558
424 1167
376 793
651 1498
495 1413
860 1479
86 1499
244 1401
93 999
870 1551
1522 1541
69 933
327 1340
124 222
218 1501
776 1459
831 1295
332 531
512 770
185 1430
1208 1449
1549 1573
700 1557
1053 1335
195 276
152 771
508 660
520 754
494 848
387 747
153 1234
514 926
56 502
201 252
637 880
1159 1298
825 949
516 1238
90 639
1172 1402
581 1257
284 311
417 1363
570 1323
515 1114
733 1534
370 747
489 1300
51 1069
451 1040
198 800
674 949
948 1425
903 960
1530 1562
549 599
422 1291
1387 1505
1437 1550
537 1325
994 1215
161 462
266 1104
1137 1248
275 890
658 1411
1016 1126
250 902
248 327
1078 1313
1145 1471
509 882
1211 1328
10 522
54 372
381 439
683 914
170 356
424 633
477 591
192 410
354 909
447 1275
231 946
291 1048
482 730
502 1526
690 1477
796 1025
1239 1491
1054 1565
310 639
27 1282
42 1497
1342 1557
393 1042
370 467
127 1174
603 816
604 1139
912 1463
161 1294
184 192
1017 1436
107 405
151 327
16 911
27 726
855 1065
206 706
453 832
521 844
378 497
184 969
161 214
68 795
1152 1201
31 360
180 514
656 1021
448 483
458 665
597 955
794 892
929 1213
29 926
161 823
240 639
899 1114
539 1097
984 1024
1128 1426
48 673
1185 1495
140 1016
846 1410
1372 1481
962 1183
423 450
80 905
146 1039
592 653
1047 1120
1199 1527
360 481
150 928
79 1081
141 523
179 251
527 777
370 786
816 833
511 554
678 1324
94 1000
405 1129
930 1413
499 1161
77 1112
1247 1528
86 485
531 1060
1067 1569
367 1513
1239 1241
329 858
194 1470
861 1456
415 750
829 1182
794 1165
455 1447
790 1463
663 872
468 1166
416 499
425 1450
614 1254
1067 1141
446 1243
923 1138
1210 1533
324 1280
98 425
123 698
539 670
987 1327
715 1528
113 528
1039 1079
532 549
139 171
463 639
258 1383
572 1032
176 1433
1208 1209
372 1445
1142 1336
181 1090
127 877
870 1454
49 654
328 948
954 1203
53 1394
395 873
312 767
341 1467
521 849
79 1009
108 1452
557 1381
954 1251
531 1582
1246 1556
1359 1452
236 1235
308 702
966 1185
1404 1503
975 1564
883 1403
375 1014
1009 1169
642 1469
399 432
115 253
193 696
1275 1281
211 1083
1014 1512
1306 1530
176 320
28 1359
376 804
1380 1546
706 1504
1203 1266
736 1552
313 555
349 831
890 1446
449 1548
60 549
1012 1502
113 932
1016 1089
917 1106
501 702
303 1132
783 1346
872 1414
1139 1584
589 1093
480 1392
573 605
1037 1353
477 1373
69 1575
249 786
616 1130
332 553
1015 1402
513 1106
1337 1398
295 1392
1095 1521
489 680
549 795
80 248
133 393
840 1151
1063 1267
244 251
127 208
550 1410
972 1083
70 369
638 984
497 1020
441 533
380 1271
613 874
728 763
83 1351
1045 1573
350 1107
31 310
142 1425
418 945
287 961
930 1297
555 903
926 1071
512 1582
233 1051
220 378
1236 1584
40 986
1140 1323
807 1546
789 1089
1177 1244
577 1240
304 1515
258 921
35 711
205 1371
408 1312
83 568
669 1572
782 1500
93 854
673 715
1209 1279
1163 1382
1523 1543
460 1462
233 1504
1371 1438
201 339
298 434
1307 1543
218 1304
575 765
805 1095
588 1544
642 1225
228 1119
468 1012
727 1162
903 1372
967 1010
1109 1249
1019 1462
276 920
613 996
266 903
88 959
95 1283
395 399
641 973
15 1545
447 610
178 848
743 901
189 642
346 1281
206 594
709 1216
493 1210
968 1457
589 1501
387 1048
188 560
366 1321
820 1406
446 577
324 1562
513 691
132 923
462 1296
567 926
52 231
562 1214
78 848
378 460
351 1544
61 1489
98 693
923 1272
1179 1390
195 1180
1357 1447
410 1017
341 718
37 706
260 911
370 503
209 547
186 289
391 1115
91 1515
891 931
209 1057
213 896
750 1392
238 561
180 1232
829 1238
563 1524
92 722
341 1118
1409 1479
954 1159
746 842
141 206
182 1429
902 1212
500 550
1315 1322
370 1508
412 1481
612 1042
129 257
213 1584
583 1380
312 1504
637 959
632 1308
976 1193
259 1404
163 176
903 1244
440 558
1005 1304
68 1028
204 708
227 1169
21 829
720 948
611 795
77 357
19 96
325 1303
277 667
122 1097
33 986
511 1517
653 852
158 1092
142 683
486 1038
755 1079
5 869
310 1102
779 841
1089 1179
108 526
504 1187
194 720
331 671
38 840
904 963
55 1047
794 1088
299 1059
771 939
474 1292
182 1385
193 301
169 1126
757 1110
607 1010
307 892
70 543
521 1082
529 745
698 757
297 1180
1175 1305
866 872
245 635
1388 1544
298 1229
611 1217
178 204
1012 1168
792 1171
484 775
929 1579
458 1437
753 1464
367 948
1335 1476
1027 1130
83 1556
379 968
1209 1275
593 899
394 741
42 1077
580 1042
300 491
157 1485
923 1096
421 1357
677 1410
111 1570
399 1287
537 935
220 622
1104 1212
231 1392
476 1185
992 1254
626 862
261 956
594 1330
549 1557
339 857
309 1411
197 1419
606 1087
392 944
922 1515
213 426
800 1170
117 823
209 851
42 735
548 1557
322 605
84 571
136 316
100 114
61 1122
1062 1338
156 1509
415 940
183 316
613 1009
748 1580
270 920
141 1407
184 579
380 502
196 376
245 997
1075 1453
748 1222
1086 1515
325 551
51 480
196 1014
191 1502
508 1156
266 569
19 484
1055 1561
89 1236
1231 1580
32 1511
853 1192
507 1126
712 1479
159 398
1126 1190
200 290
897 1543
176 1135
1286 1508
427 1219
254 1202
445 1565
204 278
296 698
677 1507
340 1250
187 896
680 766
80 1153
71 645
50 1399
258 706
6 1216
876 1124
74 958
291 1041
716 1557
403 1326
42 1491
206 417
652 1344
956 1435
176 685
88 1565
62 234
1044 1118
263 1557
513 1304
499 1169
826 885
21 1421
459 1027
194 947
349 1260
1035 1354
1329 1516
229 368
34 485
761 1122
843 1197
1039 1432
135 1173
456 1404
286 1317
90 788
600 1253
719 1205
131 1059
572 605
99 1070
235 473
194 854
506 1090
145 1019
99 1531
199 693
332 1426
857 1116
201 1540
600 819
404 716
243 1232
984 1529
454 684
672 910
112 1061
438 735
47 1343
32 633
172 403
400 1392
806 908
1283 1575
797 1025
1293 1506
88 605
291 870
723 1394
934 1203
178 1375
506 1273
82 1448
754 1484
385 690
305 867
405 1529
289 1369
261 264
77 1320
871 1353
1039 1203
1333 1429
787 1387
198 854
981 1426
1118 1377
140 1366
1392 1576
Output: 4