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