ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

УрКОП 2020

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Last Hero

Time limit: 1.0 second
Memory limit: 256 MB
A team of n people has to pick a captain. Oleg suggested an interesting way to do it.
Each team member has a digit from 0 to 9 written on their uniform. Oleg picked an integer k and then lined up the members in such a way that the digits on their uniform formed a looping sequence of digits from 0 to 9: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, …. Then he picked all the members on positions divisible by k, which are positions k, 2k, 3k, … (The first team member in the line has position 1, the last one has position n). Oleg lined all these members in a new row, keeping their relative order. Then he picked the members in the new line on positions k, 2k, 3k, … again, lined them up in a new row, and so on.
Oleg repeated this process until less than k team members remained. Then he declared the last member in the line (the one with the greatest position) as the captain. Which digit is written on the captain’s uniform?

Input

The first line contains a single integer n (1 ≤ n ≤ 109) — the number of members in the team.
The second line contains a single integer k (2 ≤ k ≤ 109) — the number that Oleg picked to determine the positions of members advancing into the next line.

Output

Output a single integer — digit on the uniform of the new captain.

Samples

inputoutput
19
3
7
123456789
321
2
10
20
9
Problem Author: Semyon Trifochkin, prepared by Daniil Zheludkov
Problem Source: Ural School Programming Contest 2020