问题描述

　　有n个小朋友围成一圈玩游戏，小朋友从1至n编号，2号小朋友坐在1号小朋友的顺时针方向，3号小朋友坐在2号小朋友的顺时针方向，……，1号小朋友坐在n号小朋友的顺时针方向。
　　游戏开始，从1号小朋友开始顺时针报数，接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数（即数的个位）为k，则该小朋友被淘汰出局，不再参加以后的报数。当游戏中只剩下一个小朋友时，该小朋友获胜。
　　例如，当n=5, k=2时：
　　1号小朋友报数1；
　　2号小朋友报数2淘汰；
　　3号小朋友报数3；
　　4号小朋友报数4淘汰；
　　5号小朋友报数5；
　　1号小朋友报数6淘汰；
　　3号小朋友报数7；
　　5号小朋友报数8淘汰；
　　3号小朋友获胜。

　　给定n和k，请问最后获胜的小朋友编号为多少？

输入格式

　　输入一行，包括两个整数n和k，意义如题目所述。

输出格式

　　输出一行，包含一个整数，表示获胜的小朋友编号。

样例输入

5 2

样例输出

3

样例输入

7 3

样例输出

4

数据规模和约定

　　对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ k ≤ 9。

样例输入

3 201711170032 201711222352
0 7 * * 1,3-5 get_up
30 23 * * Sat,Sun go_to_bed
15 12,18 * * * have_dinner

样例输出

201711170700 get_up
201711171215 have_dinner
201711171815 have_dinner
201711181215 have_dinner
201711181815 have_dinner
201711182330 go_to_bed
201711191215 have_dinner
201711191815 have_dinner
201711192330 go_to_bed
201711200700 get_up
201711201215 have_dinner
201711201815 have_dinner
201711211215 have_dinner
201711211815 have_dinner
201711220700 get_up
201711221215 have_dinner
201711221815 have_dinner

问题描述

　　小明和小芳出去乡村玩，小明负责开车，小芳来导航。
　　小芳将可能的道路分为大道和小道。大道比较好走，每走1公里小明会增加1的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走s公里小明会增加s²的疲劳度。
　　例如：有5个路口，1号路口到2号路口为小道，2号路口到3号路口为小道，3号路口到4号路口为大道，4号路口到5号路口为小道，相邻路口之间的距离都是2公里。如果小明从1号路口到5号路口，则总疲劳值为(2+2)²+2+2²=16+2+4=22。
　　现在小芳拿到了地图，请帮助她规划一个开车的路线，使得按这个路线开车小明的疲劳度最小。

输入格式

　　输入的第一行包含两个整数n, m，分别表示路口的数量和道路的数量。路口由1至n编号，小明需要开车从1号路口到n号路口。
　　接下来m行描述道路，每行包含四个整数t, a, b, c，表示一条类型为t，连接a与b两个路口，长度为c公里的双向道路。其中t为0表示大道，t为1表示小道。保证1号路口和n号路口是连通的。

输出格式

　　输出一个整数，表示最优路线下小明的疲劳度。

样例输入

6 7
1 1 2 3
1 2 3 2
0 1 3 30
0 3 4 20
0 4 5 30
1 3 5 6
1 5 6 1

样例输出

76

样例说明

　　从1走小道到2，再走小道到3，疲劳度为5²=25；然后从3走大道经过4到达5，疲劳度为20+30=50；最后从5走小道到6，疲劳度为1。总共为76。

数据规模和约定

　　对于30%的评测用例，1 ≤ n ≤ 8，1 ≤ m ≤ 10；
　　对于另外20%的评测用例，不存在小道；
　　对于另外20%的评测用例，所有的小道不相交；
　　对于所有评测用例，1 ≤ n ≤ 500，1 ≤ m ≤ 10⁵，1 ≤ a, b ≤ n，t是0或1，c ≤ 10⁵。保证答案不超过10⁶。

样例输入

1
12
0 0 10 30
1 10 10 11
1 100 10 10
2 20 10 7
2 5 10 9
4 8 5 1
5 5 5 4
7 5 1 1
3 1 200 1
6 3 22 22
9 10 99 0
11 10 6 8

样例输出

224

样例输入

10
10
0 0 981021 2878
1 2982 103544 16423
2 9309 1146606 60
1 9632 339699 4022
1 4859 1050430 27644
4 7152 1016794 8381
2 691 202924 1579
5 682 312623 1947
1 5622 434383 1966
1 1036 337962 4867
10
0 0 613160 4178
1 6039 530965 36077
1 2641 588435 10697
2 8015 1773940 21360
2 9456 1536141 20760
3 1540 1069223 6060
3 4132 1802960 9712
4 1295 338084 630
4 5977 858393 3942
5 1981 1569807 8875
10
0 0 3297948 29281
1 2838 4499071 56444
2 1723 5082712 58167
3 6932 1899951 86996
4 6111 4673596 39622
5 4854 1283153 52866
6 1600 3076850 58518
7 2887 3936856 44586
8 9662 1653482 1115
9 6359 1438146 7533
10
0 0 3827584 9067
1 1114 1938309 90351
2 1913 3135879 31961
3 210 3118784 55465
4 6982 1115456 4482
5 4326 2504229 8147
6 3567 1296569 21072
6 857 3723988 867
7 2726 1349738 682
6 2569 1465079 9994
10
0 0 4152770 20839
1 3728 1993622 104795
2 3358 1563274 31216
3 6794 2231093 43445
4 2197 2316621 7602
5 1174 2985157 7136
6 8333 103275 6346
6 5129 3083322 3511
7 469 2368248 9692
7 5732 3765843 8563
10
0 0 3091416 127451
1 2323 3358598 10828
2 8139 3723827 15116
3 9725 2486973 25964
4 1954 2821451 18368
5 8257 3938729 32443
6 2554 4006939 13576
6 5881 511102 9605
7 7999 1954660 1148
7 3260 1916815 8710
10
0 0 366406 31967
1 7426 2566312 2237
1 654 2294113 5913
2 8186 893528 10662
2 6453 1512505 13321
4 6429 616635 6615
6 5842 2578315 14449
5 3568 2988564 9781
6 1704 1044306 9036
7 4747 155934 4217
10
0 0 2481887 67676
1 2514 2068792 41590
2 5134 2460668 181
1 608 1693903 5729
2 2202 2804903 37359
5 611 1673964 6522
6 429 1245126 10648
6 7898 358662 6483
7 4194 1315545 8960
6 1193 224838 7332
10
0 0 3403835 116677
1 77 2005502 44152
2 2913 3325129 47250
2 8094 2319341 37
3 3750 458636 52717
5 8465 1635392 21518
6 9440 1757959 2079
6 8555 2306608 4397
6 5530 2658501 440
7 1594 1833614 690
10
0 0 1477756 44072
1 8380 3425538 18191
2 7951 978970 6357
1 2602 184752 6671
3 725 2947560 1525
5 1314 3589295 39573
6 1755 1675874 6532
6 8848 2470638 3789
7 1620 2129738 9070
7 9509 2363613 6569

样例输出

970205
613151
0
4682720
3959657
2626087
19106
0
1522734
5999689