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