Tận cùng nỗi đau

Nhập vào màn hình số nguyên dương \(n\). In ra các số từ \(1\) đến \(n\) theo thứ tự tăng dần bằng đệ quy.

Sử dụng đoạn code sau đây và hoàn thiện hàm đệ quy:

void output(int n){
    // Xử lý
}

int main(){
    int n; cin >> n;
    output(n);
}

Input

• Một số nguyên dương \(n\) duy nhất (\(1 \le n \le 10^5\)).

Output

• In ra các số từ \(1\) đến \(n\) trên cùng một dòng, mỗi số cách nhau bởi một dấu cách.

Example

5

1 2 3 4 5

3

1 2 3

Trong C++, kiểu dữ liệu long long thường được sử dụng để lưu các số nguyên rất lớn, với giá trị tối đa khoảng \(2^{63}-1 \approx 9.22 \cdot 10^{18}\). Tuy nhiên, trong một số bài toán, kết quả tính toán có thể còn lớn hơn giới hạn này. Khi đó, ta có thể sử dụng kiểu dữ liệu đặc biệt __int128.

__int128 là kiểu số nguyên có kích thước 128 bit, cho phép lưu các giá trị lớn hơn rất nhiều so với long long. Tuy nhiên, ta không thể sử dụng cout để trực tiếp in một biến kiểu __int128.

Hãy cài đặt hàm void out(__int128 n) có nhiệm vụ in ra màn hình giá trị của \(n\) bằng phương pháp đệ quy.

Input

• Một số nguyên \(n\) duy nhất thuộc kiểu __int128.

Output

• In ra màn hình giá trị của số nguyên \(n\).

Example

1234567890123456789

1234567890123456789

Gợi ý

Hãy thử suy nghĩ về cách biểu diễn một số nguyên bằng các chữ số từ phải sang trái. Với một số nguyên dương \(n\):

• n % 10 cho ta chữ số cuối cùng.
• n / 10 loại bỏ chữ số cuối cùng.

Để in đúng thứ tự, ta có thể sử dụng đệ quy để in các chữ số phía trước rồi mới in chữ số cuối cùng:

Lưu ý:

• Xử lý trường hợp \(n = 0\).
• Xử lý trường hợp \(n < 0\).
• Không chuyển __int128 sang string bằng thư viện có sẵn. Hãy tự xây dựng cách in số dựa trên phép chia, phép chia lấy dư và đệ quy.

Khung chương trình

#include <iostream>
using namespace std;

void out(__int128 n) {
    // TODO: Hoàn thiện hàm
}
istream& operator>>(istream& in, __int128& n) {
    string s;
    in >> s;

    n = 0;
    int sign = 1;
    int i = 0;

    if (s[0] == '-') {
        sign = -1;
        i = 1;
    }

    for (; i < s.size(); i++) {
        n = n * 10 + (s[i] - '0');
    }

    n *= sign;
    return in;
}


int main() {
    // Giả sử n được nhập vào hoặc gán giá trị
    __int128 n;
    cin >> n;
    // ...
    out(n);
    return 0;
}

Constraints

• \(-10^{38} \le n \le 10^{38}\)