Bậc thang (Staircase)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một sân khấu được xây bằng các khối lập phương giống nhau.

Các hàng của sân khấu được đánh số từ dưới lên, bắt đầu từ hàng $1$. Hàng thứ $i$ cần đúng $i$ khối lập phương.

Các hàng phải được xây theo thứ tự từ thấp lên cao. Một hàng chỉ được xem là hoàn chỉnh khi đã có đủ số khối cần thiết, và chỉ được xây hàng tiếp theo sau khi tất cả các hàng phía dưới đã hoàn chỉnh.

Cho $N$ khối lập phương. Hãy xác định:

• số hàng hoàn chỉnh lớn nhất $H$ có thể xây được;
• số khối $R$ còn thừa sau khi xây hoàn chỉnh $H$ hàng.

Input

Gồm một dòng chứa số nguyên dương $N$ — số khối lập phương hiện có.

Output

In ra hai số nguyên $H$ và $R$, cách nhau bởi một dấu cách, trong đó:

• $H$ là số hàng hoàn chỉnh lớn nhất có thể xây được;
• $R$ là số khối còn thừa sau khi xây xong $H$ hàng.

Subtask

• Subtask 1 — 20%: $1 \le N \le 10^6$.
• Subtask 2 — 30%: $1 \le N \le 10^{12}$.
• Subtask 3 — 50%: $1 \le N \le 10^{18}$.

Ví dụ

Ví dụ 1

Input

20

Output

5 5

Giải thích

Năm hàng đầu tiên cần tổng cộng

khối.

Sau khi xây xong $5$ hàng còn lại $20-15=5$ khối.

Hàng thứ $6$ cần $6$ khối nên không thể hoàn thành. Vì vậy $H=5$ và $R=5$.

Ví dụ 2

Input

21

Output

6 0

Giải thích

Sáu hàng đầu tiên cần tổng cộng

khối.

Toàn bộ $21$ khối đều được sử dụng, vì vậy có thể xây hoàn chỉnh $6$ hàng và không còn khối nào thừa. Do đó $H=6$ và $R=0$.