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