n=1000;
m=1000;
road=[|448,280|
864,712|
354,223|
592,391|
914,649|
806,850|
109,795|
680,854|
397,109|
752,256|
506,619|
406,148|
342,166|
116,180|
260,541|
374,24|
684,913|
17,75|
35,135|
397,157|
688,187|
547,738|
388,503|
442,223|
10,382|
193,978|
906,778|
934,235|
702,462|
823,546|
494,879|
731,529|
430,895|
189,576|
83,296|
429,751|
556,321|
318,811|
352,739|
817,670|
212,600|
442,655|
421,104|
582,617|
401,928|
206,124|
417,523|
610,427|
565,207|
509,37|
901,658|
455,435|
286,669|
733,280|
516,257|
779,4|
911,681|
120,342|
334,168|
626,637|
209,808|
130,222|
749,727|
335,780|
781,767|
236,194|
733,846|
20,679|
432,359|
526,433|
244,263|
624,773|
934,325|
479,561|
69,176|
886,237|
330,721|
28,471|
821,333|
613,726|
645,656|
316,478|
827,907|
732,937|
351,719|
30,279|
167,605|
51,79|
677,862|
401,580|
638,498|
142,25|
922,642|
398,879|
866,992|
781,452|
6,293|
391,242|
850,505|
261,129|
448,344|
569,437|
650,386|
729,31|
675,54|
707,785|
399,255|
220,382|
557,428|
43,262|
16,971|
284,595|
30,837|
326,199|
384,771|
860,383|
623,513|
837,134|
861,453|
219,783|
612,228|
957,472|
208,411|
629,665|
900,137|
550,608|
962,551|
588,497|
670,12|
245,751|
555,860|
356,230|
195,80|
473,790|
798,792|
961,978|
160,515|
99,471|
93,443|
16,668|
708,916|
858,299|
926,808|
13,755|
772,570|
544,501|
317,169|
890,441|
253,998|
202,508|
532,554|
956,639|
988,412|
19,100|
561,70|
225,706|
660,805|
427,19|
919,461|
560,194|
362,932|
633,104|
345,829|
449,874|
48,646|
824,202|
720,641|
538,716|
490,262|
304,217|
794,530|
571,42|
160,72|
305,410|
950,596|
536,614|
505,315|
276,462|
90,166|
528,762|
378,34|
67,862|
584,387|
678,308|
361,620|
710,896|
477,179|
785,946|
234,954|
810,958|
728,690|
37,885|
997,765|
394,871|
203,553|
295,285|
744,90|
56,944|
725,414|
586,530|
857,2|
18,75|
812,790|
84,347|
935,311|
57,319|
334,921|
607,772|
757,949|
838,82|
105,727|
101,88|
250,491|
9,787|
511,265|
245,191|
533,269|
248,590|
438,778|
226,582|
331,564|
232,766|
8,346|
563,113|
801,14|
181,76|
520,661|
221,232|
975,476|
722,673|
169,750|
287,339|
136,547|
231,763|
519,966|
525,393|
285,483|
186,663|
771,700|
803,65|
277,783|
963,884|
147,664|
709,107|
204,889|
258,631|
259,216|
138,527|
754,937|
332,326|
908,49|
250,948|
226,143|
437,979|
52,627|
777,898|
947,485|
628,575|
351,701|
309,60|
877,689|
93,273|
686,314|
179,436|
938,799|
20,221|
965,918|
287,458|
47,697|
12,387|
768,685|
929,116|
746,693|
21,381|
963,143|
84,271|
842,510|
551,78|
542,944|
714,660|
240,260|
905,578|
263,942|
384,794|
956,504|
999,39|
472,613|
618,154|
529,336|
811,365|
507,183|
439,931|
816,161|
923,602|
961,870|
715,159|
763,489|
174,714|
229,107|
48,92|
449,120|
940,197|
371,930|
315,444|
171,177|
709,995|
363,833|
515,97|
930,765|
85,332|
622,996|
126,123|
396,920|
340,328|
723,668|
278,434|
66,151|
141,809|
416,802|
680,111|
27,902|
931,554|
774,310|
318,989|
532,764|
420,836|
898,243|
378,971|
633,399|
929,367|
662,760|
968,992|
936,379|
253,814|
696,454|
870,522|
747,231|
337,54|
141,470|
170,652|
786,364|
390,517|
267,686|
654,902|
423,985|
396,736|
691,337|
447,469|
916,132|
983,580|
251,964|
716,159|
528,91|
915,266|
821,133|
631,841|
457,24|
736,942|
87,795|
822,111|
904,11|
984,463|
943,480|
299,899|
339,128|
61,140|
190,927|
459,320|
350,117|
768,102|
803,945|
596,92|
157,659|
977,774|
643,761|
474,338|
456,270|
168,459|
291,39|
310,647|
265,306|
62,66|
191,908|
729,185|
436,972|
469,319|
67,152|
796,290|
149,73|
990,390|
628,43|
973,100|
210,127|
557,32|
856,753|
51,496|
99,251|
651,759|
167,815|
195,146|
893,467|
882,443|
7,800|
421,46|
134,27|
119,805|
108,468|
871,214|
165,752|
372,535|
324,888|
385,865|
311,356|
813,11|
991,176|
274,863|
497,341|
269,46|
473,63|
139,748|
177,834|
63,531|
655,602|
571,49|
756,254|
762,58|
476,731|
142,894|
102,847|
887,439|
624,588|
926,927|
273,793|
22,964|
132,199|
416,875|
288,147|
639,493|
568,284|
453,641|
275,454|
1,997|
558,595|
812,451|
750,360|
419,994|
899,17|
200,344|
521,999|
890,844|
715,495|
486,782|
482,291|
213,651|
340,347|
818,445|
394,470|
838,766|
990,278|
920,105|
229,150|
148,667|
585,211|
29,15|
106,989|
86,559|
609,817|
403,872|
540,698|
144,364|
431,767|
918,381|
239,848|
947,501|
513,208|
696,129|
677,597|
976,5|
801,664|
672,645|
983,80|
117,451|
881,835|
953,313|
450,500|
877,85|
675,320|
156,873|
585,653|
108,825|
491,349|
643,597|
810,163|
913,86|
735,355|
590,818|
156,281|
995,121|
987,977|
154,483|
210,887|
415,15|
173,53|
804,377|
701,994|
520,33|
343,591|
181,158|
684,247|
615,353|
301,309|
135,61|
119,740|
853,579|
237,266|
283,840|
34,192|
939,616|
461,87|
155,676|
589,910|
915,708|
556,703|
986,564|
113,145|
96,490|
665,574|
695,457|
589,91|
802,444|
193,485|
671,574|
343,876|
704,70|
993,59|
809,840|
569,955|
41,872|
440,404|
917,328|
463,377|
644,699|
376,864|
657,57|
514,889|
537,998|
175,960|
296,241|
536,146|
282,747|
924,115|
412,41|
839,832|
227,740|
858,683|
330,843|
282,703|
923,52|
711,464|
614,962|
220,213|
823,885|
975,741|
103,629|
201,198|
341,72|
841,553|
925,94|
780,425|
648,855|
424,939|
370,882|
312,327|
599,71|
713,125|
548,640|
162,786|
695,891|
626,654|
302,145|
504,969|
606,38|
710,140|
22,368|
422,370|
959,171|
395,128|
45,782|
358,475|
418,118|
122,891|
687,705|
31,352|
773,854|
635,216|
636,238|
205,224|
438,187|
189,555|
324,897|
482,996|
272,713|
881,101|
758,137|
268,981|
122,29|
911,460|
164,583|
44,217|
682,813|
603,182|
826,958|
38,892|
186,348|
726,484|
820,264|
604,855|
163,706|
298,743|
55,824|
707,338|
793,544|
531,769|
212,758|
506,26|
819,988|
883,970|
666,50|
612,7|
745,488|
770,361|
366,922|
928,1000|
484,327|
182,549|
301,737|
609,698|
492,868|
65,414|
615,218|
426,914|
909,298|
95,369|
389,685|
867,722|
549,407|
828,776|
904,951|
649,307|
433,392|
36,753|
211,625|
493,18|
375,511|
593,540|
949,560|
246,126|
820,896|
577,252|
288,514|
604,222|
409,748|
74,419|
481,434|
295,279|
757,495|
804,760|
21,522|
534,669|
679,294|
800,510|
78,441|
830,796|
200,346|
354,932|
121,711|
286,849|
196,946|
533,77|
699,632|
118,323|
960,955|
415,331|
503,478|
674,242|
133,558|
724,572|
630,972|
380,907|
789,518|
110,906|
486,845|
64,880|
635,728|
832,816|
831,13|
598,735|
464,312|
965,227|
789,941|
329,953|
512,702|
744,103|
408,115|
566,446|
152,835|
545,933|
828,190|
335,249|
627,68|
271,650|
690,458|
587,139|
659,586|
405,259|
499,426|
730,185|
980,349|
720,423|
155,836|
425,53|
402,357|
601,247|
316,982|
257,350|
417,883|
518,620|
869,376|
153,479|
966,303|
445,393|
993,480|
407,874|
428,379|
637,634|
535,196|
466,192|
422,215|
348,621|
283,730|
876,2|
8,256|
599,317|
634,466|
389,815|
616,58|
345,487|
936,254|
246,587|
276,611|
865,524|
410,517|
207,897|
36,745|
512,797|
859,527|
594,979|
307,62|
313,777|
935,214|
734,418|
578,933|
565,534|
987,358|
723,853|
28,234|
380,236|
175,395|
165,219|
98,240|
95,79|
969,848|
136,688|
814,272|
775,644|
386,450|
577,903|
322,314|
941,878|
764,35|
40,959|
94,974|
5,304|
807,538|
952,359|
656,300|
435,14|
215,26|
900,912|
875,97|
746,986|
537,581|
700,592|
446,289|
275,32|
903,967|
663,124|
420,606|
198,573|
594,6|
170,375|
776,184|
293,481|
178,88|
440,682|
1,721|
693,851|
647,749|
867,610|
623,737|
305,244|
158,539|
567,255|
581,300|
605,306|
640,23|
526,884|
274,570|
717,775|
243,492|
56,831|
705,499|
694,507|
209,112|
261,697|
925,755|
360,827|
759,264|
180,241|
661,25|
123,308|
174,447|
844,172|
406,611|
981,638|
912,692|
125,739|
498,372|
833,719|
149,593|
905,863|
336,807|
204,619|
292,1000|
524,112|
784,563|
292,826|
617,502|
667,224|
734,525|
910,10|
249,712|
144,878|
248,81|
267,398|
281,584|
456,81|
756,508|
477,366|
373,799|
173,424|
548,919|
852,40|
500,980|
984,743|
973,718|
621,666|
954,3|
598,110|
572,849|
353,323|
886,888|
322,672|
787,676|
405,69|
138,834|
252,131|
938,333|
917,967|
603,830|
3,206|
591,945|
33,646|
573,542|
770,114|
625,178|
957,429|
373,474|
845,741|
468,82|
674,64|
404,868|
289,409|
188,618|
579,566|
233,683|
658,652|
106,791|
239,455|
718,583|
502,460|
509,653|
648,488|
846,689|
788,45|
76,60|
732,761|
968,151|
385,489|
738,687|
754,184|
365,546|
539,362|
400,371|
98,23|
465,357|
797,543|
692,277|
297,368|
270,487|
725,543|
825,68|
383,321|
839,233|
329,694|
859,779|
576,892|
985,201|
516,575|
691,541|
127,673|
496,791|
901,600|
724,172|
294,325|
431,130|
601,552|
55,258|
268,940|
413,717|
829,991|
96,893|
303,608|
568,413|
769,161|
792,951|
374,153|
164,948|
847,873|
921,852|
856,183|
642,205|
44,798|
895,47|
452,4|
77,89|
114,974|
9,59|
290,607|
678,238|
519,976|
402,302|
369,228|
188,552|
50,880|
630,952|
559,550|
403,562|
636,704|
784,430|
567,521|
73,162|
400,681|
465,622|
924,819|
869,197|
842,467|
742,297|
851,788|
545,388|
71,950|
74,970|
909,432|
523,982|
150,392|
494,203|
562,131|
857,83|
408,662|
367,671|
742,230|
89,411|
235,42|
861,822|
943,475|
806,355|
225,894|
866,363|
218,632|
657,843|];