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