blob: 52e49c5b75fd092aff865b1d255b6523f81cae31 [file] [log] [blame]
#define R 500
#define C 500
#define NNZ 2399
const double val[2399] = {
566,
508,
850,
780,
944,
598,
772,
880,
764,
656,
138,
757,
929,
234,
168,
629,
639,
434,
849,
793,
203,
811,
250,
770,
322,
535,
826,
609,
899,
926,
211,
755,
900,
691,
386,
821,
454,
791,
849,
256,
821,
29,
679,
944,
55,
689,
453,
631,
799,
854,
545,
97,
337,
258,
695,
667,
581,
104,
491,
517,
761,
369,
316,
42,
86,
432,
954,
736,
333,
321,
184,
920,
258,
949,
604,
907,
70,
453,
796,
102,
3,
105,
371,
388,
153,
908,
176,
567,
334,
973,
911,
323,
681,
300,
265,
711,
871,
870,
463,
969,
535,
688,
276,
908,
384,
988,
256,
416,
258,
523,
80,
911,
241,
191,
411,
127,
894,
259,
664,
129,
609,
146,
763,
109,
369,
881,
878,
224,
635,
498,
460,
363,
481,
222,
761,
489,
753,
62,
261,
389,
351,
189,
319,
557,
5,
485,
806,
119,
366,
85,
123,
918,
66,
205,
786,
313,
555,
22,
760,
904,
255,
912,
950,
676,
342,
736,
251,
170,
923,
790,
312,
716,
648,
57,
676,
972,
250,
215,
792,
798,
915,
61,
381,
897,
686,
568,
393,
969,
893,
205,
721,
684,
38,
667,
704,
750,
364,
123,
158,
892,
306,
409,
188,
394,
554,
602,
59,
9,
987,
897,
332,
873,
770,
632,
434,
598,
599,
207,
211,
410,
768,
708,
462,
687,
300,
864,
839,
183,
21,
282,
990,
578,
952,
42,
149,
235,
777,
156,
568,
400,
783,
238,
390,
108,
422,
392,
414,
338,
524,
535,
893,
160,
163,
798,
836,
662,
181,
946,
774,
113,
438,
721,
631,
577,
739,
62,
928,
523,
352,
603,
974,
291,
47,
875,
260,
754,
13,
890,
989,
104,
22,
36,
803,
39,
241,
95,
589,
603,
230,
471,
978,
617,
603,
652,
21,
755,
294,
753,
609,
494,
93,
387,
243,
128,
777,
636,
303,
665,
761,
355,
611,
605,
627,
834,
616,
59,
109,
268,
638,
117,
338,
89,
95,
4,
64,
575,
300,
783,
453,
878,
939,
984,
338,
344,
138,
291,
440,
748,
277,
628,
511,
894,
68,
412,
958,
540,
672,
935,
316,
519,
4,
613,
501,
908,
984,
820,
424,
726,
592,
526,
869,
330,
419,
28,
540,
143,
279,
79,
712,
760,
306,
806,
507,
807,
716,
729,
163,
151,
256,
873,
90,
374,
89,
122,
819,
253,
961,
62,
208,
830,
365,
231,
905,
961,
340,
928,
911,
83,
118,
864,
310,
699,
138,
221,
928,
130,
775,
425,
783,
519,
852,
187,
795,
772,
627,
709,
81,
264,
359,
149,
692,
178,
247,
51,
869,
30,
659,
190,
494,
80,
531,
883,
557,
170,
759,
331,
588,
939,
953,
407,
453,
223,
919,
147,
666,
165,
204,
924,
178,
361,
766,
455,
232,
86,
194,
536,
942,
671,
595,
420,
543,
490,
570,
547,
273,
465,
776,
845,
753,
591,
22,
320,
569,
964,
701,
483,
100,
757,
514,
850,
50,
451,
993,
79,
79,
790,
410,
409,
494,
245,
881,
676,
484,
821,
183,
45,
343,
76,
423,
855,
188,
16,
355,
159,
255,
705,
147,
400,
997,
264,
831,
644,
390,
395,
485,
457,
879,
478,
900,
187,
699,
559,
681,
947,
137,
637,
150,
700,
729,
166,
120,
325,
841,
956,
74,
576,
532,
396,
157,
327,
601,
707,
681,
813,
593,
452,
45,
936,
466,
706,
546,
265,
769,
71,
862,
37,
764,
111,
468,
844,
693,
740,
128,
19,
579,
894,
928,
160,
787,
438,
814,
274,
675,
128,
451,
626,
879,
931,
894,
57,
181,
839,
121,
728,
410,
793,
292,
566,
472,
893,
579,
986,
159,
585,
34,
485,
279,
634,
353,
626,
504,
574,
19,
54,
489,
829,
768,
246,
421,
116,
267,
801,
299,
279,
397,
331,
396,
11,
80,
682,
752,
101,
832,
673,
521,
42,
883,
663,
905,
284,
218,
59,
888,
86,
623,
878,
117,
157,
70,
309,
877,
803,
529,
666,
274,
192,
667,
558,
938,
383,
542,
237,
377,
674,
783,
638,
609,
419,
359,
309,
53,
65,
277,
526,
853,
659,
263,
280,
332,
940,
336,
748,
645,
227,
475,
945,
924,
845,
253,
798,
49,
241,
761,
379,
423,
680,
837,
116,
378,
416,
553,
802,
839,
339,
424,
40,
101,
744,
934,
119,
217,
478,
850,
998,
513,
320,
966,
306,
774,
442,
417,
646,
652,
15,
637,
199,
653,
516,
380,
983,
281,
196,
973,
604,
378,
824,
773,
835,
724,
450,
321,
446,
778,
935,
296,
752,
27,
824,
933,
145,
708,
691,
433,
627,
511,
619,
415,
263,
680,
880,
201,
700,
440,
579,
545,
445,
483,
499,
953,
518,
77,
237,
980,
923,
809,
532,
877,
965,
865,
597,
773,
378,
177,
101,
899,
448,
430,
217,
403,
21,
837,
410,
345,
606,
373,
179,
310,
634,
894,
512,
289,
946,
243,
725,
458,
680,
579,
304,
199,
721,
22,
452,
761,
945,
547,
418,
137,
209,
622,
174,
468,
223,
525,
84,
470,
266,
812,
950,
18,
983,
319,
843,
423,
862,
469,
957,
919,
387,
900,
382,
561,
337,
711,
352,
206,
737,
412,
40,
17,
851,
825,
910,
839,
207,
879,
588,
77,
867,
255,
577,
1,
609,
473,
88,
249,
491,
180,
594,
872,
870,
528,
68,
31,
208,
854,
190,
32,
200,
225,
322,
869,
425,
62,
653,
919,
138,
246,
501,
995,
133,
852,
903,
694,
482,
818,
820,
922,
839,
870,
391,
880,
478,
602,
774,
989,
139,
457,
114,
282,
632,
245,
452,
987,
920,
134,
94,
409,
124,
389,
36,
434,
885,
486,
269,
510,
487,
644,
122,
773,
13,
326,
369,
252,
407,
599,
182,
319,
229,
684,
895,
760,
703,
982,
282,
645,
835,
415,
182,
792,
681,
113,
659,
312,
998,
954,
655,
588,
3,
268,
125,
832,
346,
832,
972,
488,
709,
491,
913,
441,
187,
177,
90,
55,
959,
126,
73,
409,
606,
732,
985,
833,
381,
542,
559,
375,
829,
50,
432,
549,
996,
517,
3,
366,
33,
737,
451,
111,
380,
362,
884,
511,
199,
262,
647,
531,
717,
810,
675,
946,
614,
425,
282,
31,
436,
695,
701,
653,
629,
284,
109,
237,
909,
269,
495,
386,
327,
620,
947,
782,
663,
471,
818,
517,
768,
494,
249,
815,
725,
822,
614,
324,
22,
675,
118,
143,
929,
498,
368,
469,
482,
964,
554,
999,
265,
686,
782,
754,
247,
125,
960,
808,
788,
647,
623,
615,
727,
573,
813,
200,
371,
141,
733,
450,
515,
940,
304,
13,
522,
489,
948,
906,
529,
500,
98,
719,
174,
269,
170,
609,
789,
169,
645,
514,
438,
254,
103,
938,
306,
608,
367,
889,
667,
621,
276,
346,
736,
210,
13,
356,
914,
377,
613,
714,
949,
386,
770,
738,
310,
382,
145,
163,
470,
34,
855,
951,
672,
192,
942,
936,
429,
906,
378,
159,
665,
208,
223,
575,
977,
937,
81,
24,
484,
941,
128,
544,
811,
905,
110,
707,
806,
996,
509,
283,
493,
846,
466,
356,
807,
993,
616,
790,
163,
7,
931,
661,
353,
499,
186,
309,
107,
556,
104,
702,
61,
963,
255,
279,
454,
941,
817,
447,
786,
788,
372,
919,
14,
113,
41,
412,
744,
372,
282,
648,
248,
484,
830,
104,
742,
425,
802,
216,
561,
103,
781,
602,
201,
317,
408,
461,
91,
691,
168,
850,
935,
171,
929,
482,
790,
701,
81,
556,
85,
342,
703,
99,
937,
556,
14,
203,
974,
200,
145,
276,
408,
174,
573,
775,
893,
448,
21,
389,
813,
62,
134,
911,
119,
138,
201,
200,
105,
0,
958,
439,
635,
723,
930,
361,
745,
251,
608,
179,
19,
170,
405,
461,
643,
517,
379,
481,
899,
896,
396,
675,
536,
978,
513,
459,
454,
704,
398,
5,
786,
45,
843,
674,
758,
919,
250,
655,
980,
789,
55,
467,
459,
284,
1,
951,
447,
729,
756,
581,
992,
961,
744,
531,
169,
484,
346,
289,
18,
143,
653,
221,
669,
537,
565,
552,
874,
502,
352,
458,
183,
975,
521,
272,
336,
930,
129,
678,
670,
821,
692,
463,
175,
958,
110,
393,
123,
174,
768,
70,
942,
237,
787,
788,
462,
471,
160,
526,
579,
835,
889,
764,
878,
532,
151,
390,
607,
272,
49,
166,
399,
950,
566,
866,
446,
188,
552,
984,
530,
711,
541,
357,
30,
212,
675,
750,
746,
67,
55,
184,
788,
27,
314,
650,
403,
24,
72,
872,
260,
313,
446,
235,
275,
422,
727,
779,
192,
215,
92,
534,
619,
192,
502,
139,
125,
921,
953,
463,
909,
961,
191,
281,
619,
978,
221,
841,
540,
959,
422,
610,
323,
162,
642,
817,
961,
699,
955,
341,
480,
379,
28,
150,
386,
447,
871,
491,
632,
759,
785,
827,
50,
877,
771,
397,
67,
827,
448,
627,
85,
830,
646,
353,
304,
671,
963,
764,
58,
136,
838,
597,
932,
212,
558,
276,
73,
926,
403,
946,
268,
779,
559,
887,
213,
436,
529,
929,
295,
76,
78,
982,
105,
688,
420,
105,
815,
572,
172,
584,
412,
314,
219,
182,
238,
789,
877,
844,
62,
124,
711,
787,
315,
954,
296,
453,
842,
681,
282,
945,
132,
695,
443,
837,
92,
545,
363,
253,
515,
341,
409,
817,
578,
868,
542,
805,
508,
987,
286,
451,
157,
58,
126,
707,
874,
501,
982,
986,
382,
41,
829,
616,
895,
505,
627,
795,
555,
774,
968,
377,
762,
317,
742,
635,
481,
850,
989,
438,
72,
210,
611,
451,
521,
454,
85,
277,
797,
147,
31,
74,
621,
119,
180,
571,
234,
358,
131,
70,
857,
330,
438,
379,
166,
33,
920,
139,
316,
776,
266,
284,
247,
949,
689,
857,
534,
355,
648,
302,
840,
847,
958,
2,
602,
455,
372,
229,
370,
417,
221,
792,
91,
217,
154,
508,
45,
317,
33,
819,
48,
243,
601,
291,
613,
242,
333,
505,
537,
301,
299,
466,
927,
92,
775,
212,
985,
173,
32,
595,
643,
416,
911,
959,
252,
832,
808,
907,
761,
548,
551,
664,
728,
190,
280,
384,
822,
715,
834,
191,
437,
241,
529,
268,
38,
151,
14,
269,
679,
357,
110,
200,
393,
837,
212,
46,
336,
193,
291,
985,
975,
524,
149,
599,
424,
141,
729,
703,
238,
589,
660,
263,
319,
946,
238,
368,
728,
660,
168,
66,
679,
500,
359,
281,
159,
189,
608,
793,
204,
706,
72,
77,
660,
751,
38,
154,
437,
76,
264,
859,
216,
156,
983,
886,
802,
924,
144,
995,
643,
614,
295,
229,
125,
29,
106,
625,
27,
203,
327,
995,
123,
975,
379,
576,
258,
186,
545,
719,
530,
832,
867,
144,
146,
619,
623,
110,
218,
779,
481,
281,
826,
771,
569,
907,
342,
317,
353,
5,
360,
421,
70,
130,
42,
514,
648,
409,
909,
401,
487,
72,
580,
4,
76,
515,
382,
64,
193,
212,
20,
604,
478,
901,
784,
277,
761,
681,
429,
470,
57,
648,
609,
997,
71,
745,
876,
41,
946,
522,
339,
247,
221,
962,
110,
844,
679,
416,
522,
429,
767,
5,
819,
450,
66,
644,
722,
937,
539,
977,
727,
846,
973,
391,
699,
656,
496,
444,
173,
415,
717,
463,
935,
954,
248,
450,
892,
733,
537,
434,
920,
671,
223,
891,
252,
313,
122,
393,
156,
131,
595,
81,
71,
936,
906,
590,
187,
810,
812,
639,
626,
233,
335,
341,
253,
956,
363,
995,
971,
810,
478,
206,
382,
874,
580,
308,
178,
734,
834,
576,
938,
126,
877,
939,
274,
793,
364,
64,
347,
470,
975,
22,
14,
297,
674,
400,
8,
274,
842,
128,
102,
183,
978,
687,
614,
545,
770,
18,
353,
892,
301,
327,
497,
271,
822,
509,
154,
588,
543,
561,
632,
90,
413,
29,
462,
925,
667,
203,
846,
271,
353,
647,
434,
888,
392,
82,
445,
865,
709,
515,
382,
799,
672,
975,
466,
482,
168,
10,
150,
317,
606,
550,
166,
672,
522,
968,
605,
945,
949,
506,
353,
905,
660,
906,
490,
74,
493,
82,
47,
526,
850,
257,
308,
227,
343,
95,
260,
539,
593,
197,
304,
384,
589,
179,
553,
389,
851,
731,
831,
711,
357,
554,
982,
2,
351,
879,
42,
400,
205,
228,
328,
820,
275,
850,
320,
253,
621,
873,
842,
846,
108,
180,
300,
514,
658,
211,
373,
301,
202,
930,
489,
581,
815,
175,
738,
551,
711,
609,
343,
606,
123,
411,
851,
207,
742,
296,
741,
184,
175,
497,
32,
550,
37,
970,
526,
430,
575,
242,
934,
283,
965,
561,
702,
750,
902,
964,
711,
92,
670,
243,
188,
481,
460,
556,
886,
890,
502,
473,
8,
288,
57,
356,
721,
112,
817,
282,
123,
680,
344,
21,
935,
60,
287,
444,
267,
30,
447,
310,
922,
284,
442,
651,
454,
924,
771,
611,
852,
986,
367,
399,
115,
370,
326,
765,
323,
640,
906,
242,
526,
876,
899,
624,
166,
796,
252,
431,
99,
626,
870,
928,
935,
229,
286,
20,
648,
539,
533,
379,
64,
179,
317,
896,
293,
144,
971,
401,
720,
986,
286,
277,
828,
671,
66,
566,
461,
847,
904,
318,
59,
621,
958,
590,
905,
849,
718,
338,
342,
730,
22,
944,
544,
25,
348,
39,
719,
705,
596,
908,
805,
594,
7,
47,
744,
148,
177,
476,
866,
849,
88,
246,
438,
523,
156,
886,
758,
605,
39,
209,
29,
678,
98,
879,
286,
447,
105,
832,
303,
190,
164,
969,
222,
995,
331,
492,
399,
824,
14,
405,
831,
597,
670,
857,
120,
873,
171,
890,
905,
637,
115,
605,
336,
114,
828,
284,
303,
883,
158,
494,
153,
549,
232,
556,
695,
58,
29,
504,
252,
77,
35,
646,
137,
448,
400,
468,
237,
258,
857,
150,
981,
756,
616,
138,
188,
386,
721,
370,
71,
911,
73,
967,
568,
504,
164,
770,
100,
179,
753,
551,
67,
657,
652,
243,
444,
398,
865,
772,
427,
338,
592,
63,
536,
519,
721,
83,
212,
451,
148,
117,
98,
888,
61,
734,
672,
502,
723,
783,
345,
338,
740,
909,
505,
839,
975,
654,
804,
611,
69,
11,
523,
629,
404,
856,
620,
442,
578,
574,
149,
135,
970,
938,
492,
713,
886,
639,
454,
376,
594,
374,
530,
634,
168,
566,
809,
268,
110,
766,
381,
754,
592,
582,
283,
0,
298,
246,
854,
1,
663,
430,
801,
700,
519,
357,
169,
8,
136,
246,
613,
300,
148,
884,
563,
392,
99,
846,
824,
322,
293,
341,
555,
193,
718,
570,
822,
222,
854,
12,
226,
16,
516,
920,
639,
838,
670,
529,
485,
959,
912,
543,
706,
877,
863,
852,
351,
912,
640,
705,
697,
687,
241,
287,
290,
930,
964,
1
};
const int idx[2399] = {
220,
336,
347,
422,
44,
128,
145,
234,
259,
315,
64,
103,
378,
469,
477,
33,
108,
126,
173,
196,
328,
331,
52,
55,
109,
306,
337,
412,
443,
364,
456,
487,
496,
299,
23,
259,
67,
196,
409,
51,
77,
147,
301,
362,
26,
106,
239,
39,
81,
118,
187,
290,
339,
395,
443,
36,
45,
195,
210,
244,
273,
22,
92,
215,
306,
364,
66,
216,
5,
25,
145,
171,
330,
401,
412,
75,
148,
180,
204,
231,
432,
443,
100,
232,
400,
467,
114,
284,
300,
330,
370,
49,
135,
183,
191,
268,
423,
491,
104,
280,
393,
442,
443,
461,
136,
175,
205,
216,
466,
5,
85,
429,
491,
0,
36,
78,
95,
161,
169,
219,
231,
250,
336,
341,
360,
495,
59,
134,
213,
319,
409,
93,
104,
256,
223,
226,
8,
115,
185,
216,
320,
399,
461,
14,
60,
87,
93,
134,
170,
391,
399,
416,
455,
3,
86,
99,
304,
471,
488,
0,
102,
132,
179,
303,
312,
313,
320,
389,
279,
473,
180,
303,
310,
326,
7,
136,
239,
256,
276,
350,
21,
32,
79,
209,
270,
314,
463,
87,
134,
188,
212,
418,
13,
76,
124,
179,
409,
411,
19,
299,
207,
266,
329,
468,
29,
45,
265,
310,
384,
429,
480,
191,
347,
61,
66,
219,
228,
277,
289,
308,
402,
409,
133,
382,
488,
18,
310,
439,
206,
257,
290,
356,
443,
43,
140,
184,
187,
278,
286,
341,
354,
126,
201,
208,
239,
454,
485,
40,
87,
222,
367,
398,
457,
299,
423,
440,
44,
115,
126,
147,
291,
411,
64,
480,
1,
67,
80,
91,
163,
239,
42,
350,
361,
427,
67,
169,
270,
15,
44,
223,
378,
452,
471,
31,
67,
274,
292,
457,
58,
107,
183,
222,
347,
407,
27,
65,
84,
208,
273,
385,
441,
43,
97,
226,
305,
360,
492,
26,
88,
284,
369,
476,
21,
48,
478,
230,
312,
409,
475,
42,
53,
78,
259,
268,
489,
3,
37,
60,
141,
132,
150,
157,
328,
353,
357,
422,
466,
480,
154,
455,
295,
411,
249,
320,
359,
381,
401,
451,
210,
231,
253,
323,
330,
5,
55,
79,
105,
298,
496,
160,
229,
425,
30,
63,
115,
129,
280,
458,
31,
68,
254,
360,
420,
490,
2,
172,
180,
209,
223,
228,
265,
357,
369,
380,
443,
453,
483,
36,
110,
129,
135,
246,
305,
36,
211,
239,
254,
392,
403,
494,
255,
332,
485,
110,
360,
498,
0,
11,
37,
106,
182,
308,
14,
41,
75,
218,
256,
259,
294,
462,
218,
231,
248,
392,
427,
21,
234,
406,
29,
171,
248,
255,
352,
34,
57,
122,
173,
254,
308,
380,
393,
278,
28,
62,
129,
296,
455,
474,
15,
47,
128,
133,
300,
390,
459,
468,
35,
48,
70,
287,
299,
318,
22,
108,
171,
195,
460,
496,
188,
21,
31,
86,
338,
420,
422,
486,
495,
245,
445,
22,
85,
92,
337,
381,
387,
7,
9,
231,
425,
430,
56,
196,
344,
354,
377,
91,
107,
177,
221,
295,
321,
5,
35,
48,
90,
290,
432,
447,
51,
322,
324,
364,
482,
59,
303,
334,
444,
450,
55,
125,
319,
380,
394,
431,
82,
112,
157,
187,
261,
326,
347,
366,
18,
124,
490,
8,
218,
291,
35,
132,
322,
425,
147,
150,
242,
472,
186,
195,
201,
216,
251,
458,
33,
46,
153,
297,
298,
311,
322,
399,
426,
65,
230,
9,
32,
69,
391,
70,
126,
147,
222,
86,
261,
412,
183,
474,
110,
125,
172,
185,
402,
363,
403,
462,
40,
274,
386,
449,
333,
340,
421,
424,
410,
30,
86,
262,
374,
23,
72,
9,
47,
86,
93,
286,
304,
402,
420,
118,
265,
276,
283,
455,
20,
36,
391,
115,
137,
305,
334,
10,
188,
237,
271,
393,
422,
497,
21,
30,
99,
109,
175,
198,
467,
3,
19,
63,
82,
115,
149,
265,
24,
151,
217,
252,
307,
421,
146,
333,
381,
434,
32,
311,
361,
93,
142,
152,
395,
422,
467,
91,
181,
244,
294,
332,
390,
97,
177,
296,
323,
428,
27,
215,
318,
66,
193,
216,
333,
416,
127,
171,
209,
219,
333,
377,
401,
9,
103,
129,
135,
290,
438,
33,
107,
221,
351,
392,
406,
91,
170,
182,
313,
419,
465,
28,
74,
175,
231,
270,
30,
34,
240,
253,
63,
133,
337,
369,
416,
255,
445,
145,
350,
416,
183,
257,
414,
136,
164,
255,
300,
434,
438,
447,
60,
157,
396,
412,
25,
343,
42,
105,
361,
472,
34,
74,
136,
436,
474,
94,
177,
205,
225,
227,
319,
23,
245,
383,
426,
31,
190,
215,
228,
324,
416,
7,
12,
260,
470,
13,
290,
9,
44,
117,
166,
186,
260,
361,
372,
224,
241,
369,
1,
87,
297,
457,
29,
98,
118,
158,
226,
286,
74,
167,
241,
328,
370,
412,
454,
1,
37,
183,
228,
311,
336,
345,
413,
430,
446,
211,
327,
375,
84,
195,
219,
430,
447,
195,
384,
50,
93,
224,
349,
479,
6,
56,
105,
118,
170,
286,
468,
466,
153,
224,
240,
400,
444,
63,
158,
196,
237,
284,
296,
405,
407,
480,
26,
56,
233,
428,
370,
398,
491,
159,
184,
488,
131,
134,
138,
276,
344,
372,
428,
494,
269,
486,
136,
139,
163,
201,
253,
272,
374,
398,
487,
307,
375,
487,
168,
284,
346,
420,
451,
134,
175,
284,
88,
105,
286,
448,
96,
117,
177,
240,
285,
325,
455,
51,
228,
298,
421,
150,
433,
182,
362,
410,
58,
262,
352,
439,
43,
70,
134,
278,
152,
210,
283,
310,
333,
334,
469,
20,
42,
69,
222,
283,
320,
330,
376,
218,
285,
413,
434,
5,
175,
180,
265,
440,
474,
241,
255,
377,
479,
307,
317,
457,
0,
232,
342,
496,
25,
292,
105,
169,
208,
300,
439,
21,
65,
120,
249,
273,
191,
302,
376,
56,
92,
240,
371,
391,
446,
489,
84,
241,
322,
473,
475,
16,
92,
214,
239,
50,
158,
175,
452,
51,
360,
25,
39,
90,
99,
133,
408,
491,
430,
12,
64,
76,
189,
481,
128,
306,
442,
77,
276,
337,
356,
380,
389,
445,
61,
158,
194,
445,
303,
398,
143,
163,
199,
343,
236,
246,
340,
382,
446,
38,
154,
196,
202,
266,
367,
369,
117,
136,
250,
272,
413,
481,
0,
199,
205,
412,
39,
177,
198,
369,
448,
91,
153,
167,
187,
203,
265,
328,
218,
222,
261,
413,
419,
447,
128,
228,
498,
0,
148,
198,
486,
497,
50,
398,
457,
283,
460,
43,
116,
246,
248,
305,
447,
106,
131,
317,
126,
199,
235,
293,
34,
108,
226,
3,
108,
129,
155,
174,
162,
239,
490,
124,
214,
346,
469,
497,
274,
316,
122,
144,
149,
290,
337,
362,
371,
466,
67,
248,
276,
332,
360,
387,
405,
31,
56,
65,
90,
200,
64,
176,
203,
215,
236,
240,
337,
383,
198,
411,
431,
36,
90,
350,
356,
497,
33,
120,
130,
183,
409,
493,
8,
35,
254,
277,
321,
341,
388,
423,
497,
143,
163,
391,
446,
492,
9,
270,
42,
52,
116,
396,
456,
478,
491,
143,
148,
286,
328,
384,
35,
127,
351,
452,
7,
46,
259,
35,
290,
370,
420,
104,
258,
278,
340,
481,
169,
264,
368,
232,
471,
1,
135,
211,
152,
174,
177,
187,
292,
411,
430,
461,
4,
92,
205,
237,
247,
333,
53,
91,
289,
334,
425,
491,
118,
175,
490,
36,
361,
33,
186,
213,
471,
3,
73,
163,
409,
235,
384,
410,
470,
480,
59,
469,
97,
344,
372,
33,
107,
179,
397,
470,
291,
340,
361,
385,
25,
111,
158,
331,
471,
28,
87,
307,
69,
105,
159,
284,
311,
312,
359,
465,
17,
133,
302,
324,
274,
325,
421,
252,
4,
96,
409,
206,
246,
288,
58,
81,
150,
226,
232,
380,
168,
229,
367,
210,
248,
405,
420,
163,
212,
320,
340,
448,
68,
222,
439,
494,
70,
94,
116,
471,
284,
380,
13,
26,
120,
276,
394,
432,
492,
281,
297,
300,
355,
29,
32,
156,
182,
467,
203,
234,
420,
429,
210,
224,
248,
273,
326,
349,
37,
202,
377,
380,
43,
55,
139,
141,
170,
232,
292,
322,
77,
214,
241,
279,
326,
18,
46,
55,
107,
227,
238,
250,
146,
168,
402,
444,
459,
487,
495,
6,
121,
256,
303,
457,
461,
69,
122,
193,
204,
240,
347,
412,
418,
476,
169,
187,
400,
97,
290,
364,
394,
153,
184,
187,
9,
13,
65,
89,
120,
221,
484,
6,
120,
180,
419,
15,
86,
104,
193,
276,
324,
437,
443,
62,
97,
193,
288,
315,
318,
414,
24,
170,
189,
196,
216,
228,
270,
420,
214,
407,
466,
2,
77,
127,
188,
230,
310,
464,
469,
80,
204,
138,
171,
252,
424,
0,
95,
363,
395,
408,
430,
96,
143,
289,
97,
183,
341,
399,
460,
84,
243,
498,
28,
65,
77,
84,
139,
147,
171,
214,
256,
348,
408,
444,
449,
457,
120,
342,
38,
217,
465,
8,
212,
268,
346,
486,
491,
49,
77,
90,
222,
291,
383,
130,
405,
431,
473,
78,
290,
351,
189,
304,
498,
336,
10,
219,
257,
402,
437,
65,
69,
168,
198,
65,
241,
242,
290,
360,
402,
254,
256,
398,
407,
66,
97,
164,
222,
316,
390,
429,
24,
81,
133,
207,
313,
67,
108,
204,
303,
494,
43,
194,
198,
285,
294,
347,
356,
394,
83,
92,
147,
167,
386,
20,
225,
400,
172,
363,
99,
64,
373,
377,
6,
63,
206,
107,
149,
230,
428,
41,
56,
77,
78,
311,
413,
476,
477,
81,
130,
145,
167,
247,
416,
56,
289,
339,
27,
47,
132,
309,
392,
36,
55,
73,
352,
358,
25,
58,
352,
430,
58,
171,
221,
334,
379,
453,
288,
479,
109,
134,
143,
174,
285,
313,
468,
495,
258,
289,
334,
382,
483,
46,
136,
264,
417,
458,
36,
59,
88,
173,
310,
316,
354,
471,
46,
225,
262,
335,
364,
468,
121,
341,
349,
7,
14,
21,
99,
135,
142,
207,
209,
272,
294,
456,
491,
208,
248,
321,
43,
129,
188,
362,
191,
279,
294,
307,
324,
362,
140,
422,
56,
169,
188,
232,
328,
449,
14,
134,
369,
375,
48,
164,
224,
260,
20,
93,
157,
219,
262,
274,
362,
473,
484,
103,
125,
140,
174,
175,
191,
226,
358,
408,
450,
20,
94,
289,
310,
311,
448,
478,
36,
175,
185,
337,
391,
48,
72,
184,
233,
345,
485,
231,
242,
339,
451,
456,
152,
158,
398,
458,
488,
151,
240,
357,
1,
33,
139,
141,
177,
223,
289,
479,
90,
115,
461,
480,
24,
26,
44,
72,
213,
361,
445,
34,
119,
470,
19,
56,
405,
464,
47,
112,
163,
235,
342,
462,
103,
192,
225,
23,
458,
68,
270,
363,
422,
427,
449,
450,
477,
105,
131,
139,
198,
212,
413,
429,
435,
43,
278,
19,
113,
192,
327,
347,
44,
67,
160,
225,
263,
330,
344,
158,
274,
303,
317,
350,
379,
409,
33,
53,
217,
273,
304,
352,
461,
495,
101,
168,
370,
395,
458,
156,
301,
319,
324,
347,
73,
127,
253,
272,
128,
212,
237,
257,
351,
77,
106,
216,
270,
368,
371,
400,
223,
355,
384,
30,
268,
307,
368,
79,
300,
317,
327,
15,
376,
31,
80,
160,
206,
227,
103,
231,
435,
481,
499,
182,
186,
189,
442,
7,
59,
65,
117,
225,
298,
304,
364,
457,
489,
186,
198,
265,
309,
336,
391,
457,
314,
418,
81,
133,
186,
190,
227,
258,
277,
419,
492,
82,
222,
239,
315,
71,
92,
122,
220,
252,
272,
311,
391,
433,
97,
137,
244,
267,
426,
34,
202,
234,
426,
428,
51,
109,
267,
377,
382,
107,
166,
203,
337,
0,
127,
247,
404,
64,
94,
373,
430,
448,
17,
37,
57,
102,
352,
354,
114,
174,
193,
241,
284,
74,
94,
213,
238,
475,
476,
140,
247,
280,
302,
328,
49,
197,
201,
222,
280,
457,
167,
445,
465,
478,
499,
25,
215,
438,
8,
129,
153,
171,
316,
328,
158,
215,
303,
328,
353,
479,
62,
251,
271,
4,
119,
262,
303,
311,
405,
419,
277,
461,
236,
248,
445,
15,
108,
227,
309,
362,
378,
424,
78,
94,
109,
118,
124,
247,
253,
315,
478,
13,
154,
170,
331,
365,
386,
264,
268,
300,
305,
429,
463,
499,
52,
105,
135,
181,
111,
156,
183,
231,
350,
388,
461,
291,
360,
80,
106,
138,
197,
242,
255,
260,
381,
415,
447,
499,
41,
266,
341,
391,
410,
448,
495,
58,
146,
286,
351,
419,
436,
464,
483,
251,
252,
444,
492,
184,
200,
57,
75,
170,
186,
187,
275,
314,
364,
407,
162,
173,
232,
211,
355,
445,
448,
308,
98,
280,
397,
431,
112,
122,
157,
209,
338,
388,
429,
112,
213,
349,
470,
69,
70,
119,
222,
251,
453,
81,
173,
482,
105,
147,
10,
229,
462,
467,
98,
421,
479,
203,
498,
499,
93,
130,
142,
270,
278,
336,
419,
73,
134,
142,
177,
192,
335,
490,
45,
140,
143,
195,
274,
284,
324,
56,
94,
171,
28,
135,
258,
277,
284,
333,
370,
421,
432,
465,
31,
46,
222,
331,
387,
432,
18,
56,
82,
95,
258,
261,
356,
378,
484,
60,
285,
298,
347,
0,
200,
307,
372,
2,
89,
201,
291,
298,
382,
455,
121,
145,
155,
47,
226,
236,
396,
398,
137,
311,
381,
429,
45,
109,
141,
173,
207,
464,
471,
499,
37,
45,
268,
447,
496,
41,
163,
387,
484,
30,
48,
91,
146,
261,
313,
401,
11,
78,
122,
144,
450,
499,
75,
82,
131,
218,
257,
285,
294,
362,
442,
213,
255,
291,
492,
63,
80,
282,
418,
1,
60,
87,
102,
111,
180,
272,
281,
324,
380,
458,
185,
216,
475,
12,
62,
109,
143,
195,
257,
271,
324,
385,
410,
226,
330,
404,
54,
158,
374,
221,
320,
340,
86,
93,
236,
94,
159,
238,
242,
318,
356,
40,
75,
168,
211,
294,
32,
164,
174,
198,
421,
13,
102,
314,
379,
418,
439,
485,
6,
53,
104,
123,
208,
436,
452,
59,
141,
204,
402,
498,
134,
335,
429,
240,
391,
461,
14,
16,
46,
371,
376,
37,
172,
227,
343,
397,
435,
39,
136,
202,
262,
339,
445,
474,
145,
272,
342,
121,
127,
12,
125,
155,
186,
234,
64,
96,
97,
108,
213,
350,
410,
485,
35,
56,
57,
167,
169,
399,
478,
60,
103,
307,
92,
104,
150,
211,
260,
8,
64,
73,
222,
273,
423,
179,
184,
190,
193,
265,
271,
305,
318,
344,
14,
75,
124,
317,
343,
404,
4,
141,
167,
212,
496
};
const double x[500] = {
737,
519,
538,
486,
557,
31,
651,
101,
310,
729,
721,
164,
577,
411,
104,
891,
988,
370,
788,
898,
576,
674,
7,
10,
91,
253,
9,
54,
105,
36,
799,
188,
651,
92,
766,
394,
8,
823,
242,
334,
639,
462,
111,
847,
919,
681,
392,
657,
358,
203,
453,
897,
965,
316,
759,
894,
893,
44,
743,
736,
970,
473,
229,
120,
485,
174,
405,
514,
984,
200,
723,
867,
259,
997,
191,
340,
75,
763,
579,
216,
154,
331,
338,
184,
786,
56,
235,
880,
810,
544,
522,
358,
219,
566,
632,
422,
636,
760,
657,
117,
138,
228,
163,
336,
572,
722,
438,
280,
234,
454,
967,
148,
325,
142,
790,
3,
497,
770,
936,
101,
696,
108,
255,
140,
320,
29,
36,
228,
468,
24,
183,
844,
513,
856,
102,
9,
526,
50,
73,
366,
599,
246,
662,
473,
651,
568,
575,
972,
352,
341,
897,
15,
73,
764,
768,
879,
886,
906,
718,
621,
529,
282,
339,
165,
137,
999,
215,
33,
639,
999,
906,
210,
62,
655,
996,
675,
552,
333,
176,
426,
891,
638,
571,
715,
18,
708,
795,
26,
31,
250,
18,
949,
183,
968,
394,
580,
766,
686,
162,
134,
185,
943,
919,
577,
539,
180,
750,
285,
591,
881,
381,
118,
852,
696,
617,
941,
767,
592,
650,
74,
961,
881,
891,
71,
905,
575,
598,
523,
477,
561,
948,
762,
570,
773,
146,
894,
203,
610,
471,
669,
189,
473,
650,
606,
385,
288,
360,
648,
115,
836,
139,
530,
248,
331,
286,
849,
812,
356,
884,
33,
57,
147,
297,
826,
916,
581,
0,
918,
81,
12,
956,
309,
550,
15,
243,
294,
893,
290,
227,
826,
843,
789,
744,
494,
742,
643,
126,
861,
444,
506,
417,
215,
246,
9,
244,
283,
595,
635,
494,
612,
737,
311,
896,
834,
222,
121,
595,
680,
309,
729,
263,
142,
804,
262,
343,
179,
649,
118,
360,
536,
669,
429,
359,
667,
313,
671,
506,
951,
461,
291,
359,
237,
727,
143,
968,
769,
97,
842,
752,
803,
299,
154,
384,
23,
567,
339,
778,
492,
116,
320,
967,
526,
66,
761,
908,
345,
885,
193,
894,
547,
124,
18,
254,
947,
192,
111,
384,
204,
338,
574,
749,
816,
717,
457,
353,
163,
979,
896,
679,
342,
932,
100,
216,
531,
320,
122,
594,
956,
638,
450,
733,
643,
293,
891,
633,
901,
815,
676,
307,
144,
286,
106,
182,
605,
575,
129,
390,
212,
843,
225,
544,
468,
203,
223,
862,
795,
36,
348,
743,
528,
904,
126,
802,
82,
156,
369,
986,
332,
977,
570,
421,
345,
401,
480,
63,
518,
667,
31,
909,
552,
994,
314,
891,
642,
439,
132,
670,
402,
263,
140,
549,
905,
712,
299,
986,
86,
709,
786,
47,
679,
864,
13,
140,
659,
479,
838,
988,
846,
855,
367,
935,
657,
453,
400,
851,
749,
500,
673,
523,
708,
568,
76,
18,
589,
689,
195,
504,
402,
835,
705,
187,
615,
482,
160,
609,
761,
907,
294,
538,
545
};
const int ptr[501] = {
0,
4,
8,
10,
15,
22,
29,
33,
34,
36,
39,
44,
44,
47,
55,
61,
66,
68,
75,
82,
86,
91,
98,
104,
109,
113,
126,
131,
134,
136,
143,
153,
159,
168,
170,
174,
176,
180,
187,
192,
198,
200,
204,
211,
213,
222,
225,
228,
233,
241,
247,
253,
256,
262,
264,
270,
274,
277,
283,
288,
294,
301,
307,
312,
315,
319,
325,
329,
332,
338,
340,
342,
348,
353,
359,
362,
366,
368,
374,
387,
393,
400,
403,
406,
412,
420,
425,
428,
433,
441,
442,
448,
456,
462,
468,
469,
477,
479,
485,
490,
495,
501,
508,
513,
518,
524,
532,
535,
538,
542,
546,
552,
561,
563,
567,
571,
574,
576,
581,
584,
588,
592,
593,
597,
599,
607,
612,
615,
619,
626,
633,
640,
646,
650,
653,
659,
665,
670,
673,
678,
685,
691,
697,
703,
708,
712,
717,
719,
722,
725,
732,
736,
738,
742,
747,
753,
757,
763,
767,
769,
769,
777,
780,
784,
790,
797,
807,
810,
813,
815,
817,
822,
829,
830,
835,
844,
848,
851,
854,
862,
864,
873,
876,
881,
884,
888,
895,
899,
901,
904,
908,
912,
919,
927,
931,
937,
941,
944,
948,
950,
955,
960,
963,
970,
975,
979,
983,
985,
992,
993,
998,
1001,
1008,
1012,
1014,
1018,
1023,
1030,
1036,
1040,
1045,
1052,
1058,
1061,
1066,
1069,
1071,
1077,
1080,
1084,
1087,
1090,
1092,
1095,
1100,
1102,
1110,
1117,
1122,
1130,
1133,
1138,
1142,
1144,
1146,
1153,
1158,
1160,
1167,
1172,
1176,
1179,
1183,
1188,
1191,
1193,
1196,
1204,
1210,
1216,
1219,
1221,
1225,
1229,
1234,
1236,
1239,
1244,
1248,
1253,
1256,
1264,
1268,
1271,
1272,
1275,
1278,
1284,
1287,
1291,
1296,
1300,
1304,
1306,
1313,
1317,
1322,
1326,
1332,
1336,
1344,
1349,
1356,
1363,
1368,
1369,
1378,
1381,
1385,
1388,
1395,
1399,
1407,
1414,
1422,
1425,
1433,
1435,
1438,
1439,
1445,
1448,
1450,
1453,
1456,
1470,
1472,
1475,
1481,
1487,
1491,
1494,
1497,
1498,
1503,
1507,
1513,
1517,
1524,
1529,
1534,
1542,
1547,
1550,
1550,
1552,
1553,
1556,
1559,
1563,
1571,
1577,
1580,
1585,
1590,
1594,
1598,
1600,
1602,
1610,
1615,
1620,
1628,
1634,
1637,
1649,
1652,
1656,
1662,
1664,
1670,
1674,
1678,
1687,
1697,
1704,
1709,
1715,
1720,
1725,
1728,
1736,
1740,
1747,
1750,
1754,
1760,
1763,
1765,
1773,
1781,
1783,
1788,
1795,
1802,
1810,
1815,
1820,
1824,
1829,
1836,
1839,
1843,
1847,
1849,
1854,
1859,
1863,
1873,
1880,
1882,
1891,
1895,
1899,
1904,
1909,
1914,
1919,
1923,
1927,
1932,
1938,
1943,
1949,
1954,
1960,
1965,
1968,
1974,
1980,
1983,
1990,
1992,
1995,
2002,
2011,
2017,
2024,
2028,
2035,
2037,
2048,
2055,
2063,
2067,
2069,
2078,
2081,
2085,
2086,
2090,
2097,
2101,
2107,
2110,
2112,
2116,
2119,
2122,
2129,
2136,
2143,
2146,
2156,
2162,
2171,
2175,
2179,
2186,
2189,
2194,
2198,
2206,
2211,
2215,
2222,
2228,
2237,
2241,
2245,
2256,
2259,
2269,
2272,
2275,
2278,
2279,
2281,
2287,
2292,
2297,
2304,
2311,
2316,
2319,
2322,
2327,
2333,
2340,
2343,
2345,
2350,
2358,
2365,
2365,
2368,
2373,
2379,
2388,
2394,
2399
};
const double verify_data[500] = {
1636962,
1714376,
142636,
1151015,
1672341,
2790420,
1447201,
422892,
30953,
1030287,
1335188,
0,
605334,
2278445,
858848,
245423,
950882,
705076,
1312024,
1084284,
1837558,
1201746,
2360392,
1488940,
688178,
2632122,
1481444,
660854,
346453,
982949,
1400599,
1093225,
2856372,
1078398,
1074402,
579548,
1820752,
2638601,
2072665,
749887,
687788,
478788,
1482258,
1207317,
1397243,
794364,
1002505,
1651686,
1028801,
1189726,
1513197,
1214956,
738475,
633771,
1207042,
680857,
899314,
2277406,
773143,
1986687,
907216,
907940,
1539019,
1043338,
681730,
219905,
1397298,
2184201,
1537202,
266744,
563005,
1827909,
1105928,
2286680,
887533,
343193,
238910,
1678393,
2600003,
417502,
1551071,
798273,
398719,
2056881,
1296314,
917292,
190534,
882078,
1979139,
50621,
1048185,
1967771,
1911887,
1895897,
23343,
2658748,
285864,
1027049,
975769,
2488413,
832738,
844130,
1379856,
1785889,
2463463,
782430,
982466,
609500,
706251,
1981399,
1861430,
2146667,
250104,
1166284,
1295022,
189599,
855191,
1005718,
969658,
707377,
561273,
86496,
717937,
97767,
1893638,
779229,
429727,
99564,
1863565,
2267656,
950026,
780700,
581248,
393282,
2134865,
1244700,
1894843,
954212,
1439102,
779512,
1459287,
881497,
2202043,
1447401,
1249637,
765168,
488244,
837127,
1236555,
2281259,
1995666,
25783,
534020,
1486259,
1268571,
875283,
744594,
1410335,
757320,
0,
1922627,
399058,
1490594,
1475527,
1587557,
1695667,
644546,
536038,
224304,
414120,
2029077,
3930385,
377416,
1059074,
1960417,
1439575,
368749,
460183,
2479302,
105204,
1426355,
649313,
2194338,
918200,
1591449,
2229266,
434520,
684504,
1009270,
222922,
600674,
1011867,
1321434,
836127,
2493805,
1448674,
1269364,
1304961,
98554,
2423810,
1570229,
302458,
2806045,
1534004,
1463827,
1085011,
120989,
1701753,
110302,
938429,
1186733,
2255246,
425960,
376311,
341394,
1061333,
2025091,
522270,
598604,
1000824,
2254049,
1857539,
346425,
1345187,
550497,
1251096,
943720,
681558,
555972,
779590,
299796,
1445763,
459865,
774572,
489448,
2407693,
1574903,
1630452,
1907397,
555045,
1902494,
1172223,
142555,
445864,
1376151,
1200389,
327553,
1548402,
1106503,
888650,
41081,
1245270,
845610,
1232215,
387441,
434475,
1204003,
1333189,
1672468,
567827,
11392,
631046,
1299298,
719608,
714169,
362247,
1308257,
530903,
398202,
885445,
2606806,
1354354,
438760,
194928,
712863,
1010340,
2245646,
376041,
876890,
1683404,
955032,
1065455,
925034,
1731713,
1152271,
2093865,
1221433,
629438,
2054936,
2643313,
1322567,
1492288,
1844514,
1802382,
871,
1350044,
967406,
756881,
574442,
1295864,
1815978,
2822668,
2201377,
2729436,
616018,
2318346,
332717,
289665,
97812,
1881483,
1003188,
702530,
409314,
645118,
3645947,
723792,
503126,
1609036,
1647277,
587437,
735899,
666552,
27354,
1045106,
397951,
1087090,
1173872,
1629962,
1334261,
1855668,
2856970,
1341188,
336968,
0,
521349,
53118,
881926,
154917,
942966,
1237636,
820836,
579583,
1436861,
2025006,
634434,
829152,
298073,
205380,
1622350,
1171051,
848451,
2417009,
2016092,
390510,
2721874,
359761,
309038,
1061522,
297026,
1311767,
305305,
854945,
1773244,
2656339,
896058,
1069160,
1552917,
1421821,
440874,
216699,
1654864,
521705,
807422,
1242602,
1329872,
308130,
526463,
27937,
1450630,
1621987,
799154,
1378289,
2519996,
1149046,
579937,
1841561,
1895047,
1009234,
1922198,
2570006,
409696,
442495,
277484,
979605,
1392287,
1023715,
1881778,
2432703,
2297384,
542451,
1368100,
833048,
1038108,
742376,
1542317,
2230186,
1249077,
884020,
1286059,
1102407,
1651393,
1787846,
1370154,
2734166,
2935249,
447485,
736859,
828966,
1547038,
765990,
1427773,
255456,
134871,
1597546,
2173052,
1187286,
2364828,
1220233,
1760369,
75080,
2799969,
1363310,
2347168,
272279,
33698,
1192053,
342501,
356092,
136578,
1701048,
2216796,
1340150,
1852854,
580862,
407410,
1860346,
200649,
954363,
955621,
2234154,
2007706,
646339,
2712491,
1259244,
2368138,
1550431,
1160903,
987838,
650293,
833228,
368144,
1998925,
1733716,
1050000,
1061635,
1144649,
1260205,
851043,
1417512,
2826918,
1059350,
1522135,
1039943,
703837,
1035006,
19505,
211545,
1461101,
1238659,
1414306,
1151385,
2169011,
1101116,
1118290,
335296,
1502266,
1405699,
1762457,
530338,
246108,
484583,
2164048,
1614511,
0,
1446940,
575450,
2043329,
2057251,
774670,
1084124
};