Truy vấn với mảng

Bối cảnh

Bài toán được mô tả qua yêu cầu và dữ liệu dưới đây.

Yêu cầu

Bạn được cung cấp một mảng \(a\) có độ dài vô hạn. Ban đầu tất cả các phần tử đều bằng \(0\). Yêu cầu xử lý \(Q\) truy vấn có dạng như sau:

• 0 k v nghĩa là gán \(a[k] = v\).
• 1 k nghĩa là in ra giá trị \(a[k]\).

Input

Dòng đầu tiên chứa giá trị \(Q\) \((1 \leq Q \leq 10^5)\)

\(Q\) dòng tiếp theo chứa các truy vấn \((0\leq k, v \leq |10^{18}|)\).

Output

Với truy vấn 1 k in ra giá trị \(a[k]\)

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

8
0 1 2
1 1
1 2
0 2 3
1 1
1 2
0 2 1
1 2

Output

2
0
2
3
1

Giải thích ví dụ

• Ví dụ: Các truy vấn 0 k v cập nhật giá trị tại chỉ số k với giá trị v, và các truy vấn 1 k in ra giá trị hiện tại tại chỉ số k.

Thông tin học tập

• Buổi: B15
• Concepts: map/set, large-key queries
• Giới hạn kiến thức: B01-B15
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 15