Đặt:

\(u_1=1\)

\(u_2=12\)

\(u_3=123\)

\(u_4=1234\)

...

\(u_9=123456789\)

\(u_{10}=1234567891\)

\(u_{11}=12345678912\)

...

\(u_{18}=123456789123456789\)

\(u_{19}=1234567891234567891\)

\(u_{20}=12345678912345678912\)

...

Gọi \(S\) là xâu được tạo ra bằng cách nối liên tiếp các xâu \(u_1,u_2,u_3,...\) (Độ dài của xâu \(S\) là vô tận)

\((S=112123123412345123456...)\)

Ví dụ Với \(n=16\) thì thì số thứ 16 trong \(S\) là số \(1\) nên kết quả ra số \(1\)

Yêu cầu: Cho trước số nguyên dương \(n\). Hãy in ra kí tự thứ \(n\) của xâu \(S\) (biết rằng, xâu \(S\) được đánh chỉ số bằng đầu từ \(1\))

Input

• Một dòng thứ nhất chứa số \(n\ (1\le n\le 10^9)\)

Output

• In ra đáp án cần tìm

Example

10

4

Scoring

• \(60\%\) : \(1\le n\le 1000000\)
• \(40\%\) : Không có điều kiện gì