Mã Morse là một phương pháp được sử dụng trong viễn thông để mã hóa văn bản ký tự như trình tự chuẩn của hai khoảng thời gian tín hiệu khác nhau, được gọi là dấu chấm và dấu gạch ngang hoặc dot và dash.

Mã Morse quốc tế mã hóa 26 chữ cái tiếng Anh từ A đến Z, một số chữ cái không phải tiếng Anh, chữ số Ả Rập và một tập hợp nhỏ các dấu câu và tín hiệu thủ tục, được thể hiện qua ảnh sau:

TaThanHungbc là một người rất đam mê các trò chơi mã số. Anh ấy có một vài ký tự đã được mã hóa qua mã Morse. Nhiệm vụ của bạn là giải mã những đoạn mã này.

~\texttt{Input}~

• Gồm một dòng duy nhất chứa 1 ký tự được mã hóa.

~\texttt{Output}~

• Gồm một dòng duy nhất là ký tự đó khi được giải mã. (26 chữ cái tiếng Anh được viết in hoa từ ~A~ đến ~Z~ hoặc 10 chữ số từ ~0~ đến ~9~).

~\texttt{Constraint}~

• Tất cả các ký tự được mã hóa điều có trong bảng trên.

~\texttt{Sample Input}~

---

~\texttt{Sample Output}~

O

vvngh là một nhà sưu tầm đá lỗi lạc. Mỗi viên đá có một sức mạnh X khác nhau. Sức mạnh X của viên đá được đặc trưng bởi hai chỉ số thực tại L và mơ hồ R có thể được xác định bằng công thức sau: $${\sum^{R}_{i=L}i} = X (L < R)$$ Ví dụ, với viên đá sức mạnh ~X = 9~ ta có thể xác định được hai chỉ số tương ứng là ~L = 2~ và ~R = 4~ vì ~2 + 3 + 4 = 9~. Nhiệm vụ của bạn là xác định hai chỉ số này với mỗi viên đá sức mạnh X.

~\texttt{Input}~

• Một số nguyên ~X~ duy nhất là sức mạnh của viên đá.

~\texttt{Output}~

• Một dòng duy nhất chứa hai số ~L~ và ~R~ là chỉ số của viên đá (~|L|~, ~|R| \leq 10^{12}~).
• Nếu tồn tại nhiều đáp án, hãy trả lời một đáp án bất kỳ.
• Nếu không tồn tại hai chỉ số này thì in ~-1~.

~\texttt{Constraint}~

• ~1 \leq |X| \leq 10^{12}~.

~\texttt{Subtask}~

• Subtask ~1~ (~50\%~ số điểm): ~|X| \leq 10^3~.
• Subtask ~2~ (~50\%~ số điểm): Giới hạn gốc.

~\texttt{Sample Input}~

9

~\texttt{Sample Output}~

2 4

CodeTN vừa mua được một mẻ cá thập cẩm từ một ngư dân nọ, cậu ta đem thả tất cả chúng vào bể tạo thành một quần xã. Nhưng sau một thời gian vì mỗi quan hệ đối kháng (động vật ăn động vật) bể cá của cậu ta chỉ còn lại một vài con. Lúc này CodeTN bỗng nghĩ ra một câu đố dành cho mọi người:

Giả sử bể cá có dạng ~2D~ với tọa độ được đánh số từ ~1~ đến ~10 ^ 6~. Mỗi con cá có ~2~ chỉ số là ~l, r~ (~1 \le l \le r \le 10 ^ 6~), tức chiều dài con cá khi nhìn vào bể bắt đầu từ ~l~ và kết thúc tại ~r~, và có điểm ~\texttt{HP}~ bằng điểm ~\texttt{HP}~ con cá lớn nhất mà nó ăn cộng ~1~ (nếu chưa ăn con cá nào khác thì có điểm ~\texttt{HP}~ sẽ mặc định là ~1~). Luật ăn cá được quy ước như sau nếu ~2~ con cá có cùng ~l, r~ thì con có chỉ số lớn hơn sẽ ăn con có chỉ số bé hơn. Ngược lại, thì cá ~v~ ăn cá ~u~ nếu (~l_v \le l_u \le r_u \le r_v~). Ở đây, tạm chấp nhận là một con cá có thể bị ăn bởi nhiều con khác.

Yêu cầu: Tìm điểm số lớn nhất có thể.

~(*333)<<~ (Hình ảnh chỉ mang tính chất minh họa)

~\texttt{Input}~

• Dòng đầu tiên chứa số nguyên dương ~n~ (~n \le 10 ^ 6~) , là số con cá được mua về.

• Dòng thứ i trong số ~n~ dòng sau, chứa 2 số nguyên ~l,r~ biểu thị cho con cá thứ ~i~.

~\texttt{Output}~

• Một số duy nhất là kết quả của bài toán.

~\texttt{Subtask}~

• Subtask ~1~ (~10\%~ số điểm): ~n \leq 10~.
• Subtask ~2~ (~50\%~ số điểm): ~n \leq 1000~.
• Subtask ~3~ (~40\%~ số điểm): Không có giới hạn gì thêm.

~\texttt{Sample Input}~

3 
1 6
2 5 
3 4

~\texttt{Sample Output}~

3

Sau khi trở về từ hang ~\texttt{MU}~ bằng cánh của thần kỳ của ~\texttt{Doraemon}~, CodeTN lại VÔ TÌNH lạc vào một thế giới ~\texttt{Mơ màng}~ với ~n~ thành phố đánh số từ ~1~ đến ~n~. Mỗi thành phố có nhiệt độ ~t_i~ và giá trị ~\texttt{"lạ"}~ ~a_i~. Bây giờ CodeTN đang đứng ở thành phố ~0~ với nhiệt độ và độ ~\texttt{"lạ"}~ bằng ~0~. Ở mỗi bước, có thể nhảy đến thành phố bất kì có chỉ số lớn hơn thành phố hiện tại. Hãy giúp CodeTN tìm chênh lệch nhiệt độ giữa hai thành phố liên tiếp nhỏ để tồn tại con đường đi đến thành phố ~n~ nhưng luôn đảm bảo là tổng độ ~\texttt{"lạ"}~ các thành phố đã đi qua luôn không âm.

~\texttt{Input}~

• Dòng đầu là số thành phố ~n~ (~n \le 1000~).

• n dòng tiếp theo mỗi dòng gồm ~2~ số ~t_i, a_i~ ( ~-10^6 \le t_i, a_i \le 10^6~).

~\texttt{Output}~

• In ra chênh lệnh ít nhất có thể, nếu không in ~-1~.

~\texttt{Subtask}~

• Subtask ~1~ (~20\%~ số điểm): ~n \leq 10~.
• Subtask ~2~ (~80\%~ số điểm): Không có giới hạn gì thêm

~\texttt{Sample Input}~

3 
-3 -2 
-3 3 
3 -1

~\texttt{Sample Output}~

6

Mùa hè năm 2024 là mùa hè cuối cùng và nhiều kỉ niệm nhất của CodeTN ở Việt Nam, vì sau đó cậu sẽ đi du học một thời gian khá dài. CodeTN sẽ kết được nhiều bạn mới và có nhiều trải nghiệm hơn ở vùng đất xa quê, đổi lại thì cậu sẽ hiếm khi có cơ hội được gặp mặt với những người bạn thân yêu. Vì vậy, trước khi đi CodeTN sẽ tặng cho những người bạn mình một thùng quà gồm nhiều hộp quà kỉ niệm nhỏ nhằm để các bạn luôn nhớ về cậu ấy.

Ban đầu, số hộp quà trong một thùng quà sẽ khác nhau tùy theo mức độ thân thiết của CodeTN với người bạn đó. Tuy nhiên những người bạn của CodeTN quen biết nhau và có thể sinh lòng đố kị khi người khác nhận được nhiều quà hơn mình. Vì vậy cậu quyết định thêm hoặc bớt số quà trong một số thùng quà để tất cả thùng quà đều có số hộp quà giống nhau. Thật không may là CodeTN đã đóng gói tất cả kiện hàng nên khi muốn thêm hoặc bớt một hộp quà trong một kiện hàng sẽ tốn chi phí nhất định.

Bạn hãy giúp CodeTN tìm chi phí nhỏ nhất để làm cho tất cả thùng quà của cậu ấy có số hộp quà bằng nhau.

~\texttt{Input}~

• Dòng đầu tiên chứa số nguyên ~n~ là số thùng quà CodeTN đã chuẩn bị.
• Dòng tiếp theo chứa ~n~ số nguyên, cho biết thùng quà thứ ~i~ có ~a_i~ hộp quà.
• Dòng cuối cùng chứa ~n~ số nguyên, cho biết chi phí thêm hoặc bớt một hộp quà trong thùng quà thứ ~i~ là ~t_i~.

~\texttt{Output}~

• Gồm một số nguyên duy nhất là chi phí ít nhất để các thùng quà có số hộp quà bằng nhau.

~\texttt{Sample input}~

4
1 2 3 2
5 2 2 1

~\texttt{Sample output}~

7

~\texttt{Constraint}~

• ~1 \le n \le 10^7~.
• ~1 \le a_i \le 10^7~.
• ~1 \le t_i \leq 10^6~.

~\texttt{Subtask}~

• Subtask ~1~ (~20\%~): ~n, a_i \leq 100~.
• Subtask ~2~ (~60\%~): ~n, a_i \leq 10^6~.
• Subtask ~3~ (~20\%~): ~n, a_i \leq 10^7~.

~\texttt{Note}~

• Chi phí để đưa tất cả thùng quà về còn ~2~ món quà là: ~C = 5 \times (2 - 1) + 2 \times (2 - 2) + 2 \times (3 - 2) + 1 * \times (2 - 2) = 5 \times 1 + 2 \times 0 + 2 \times 1 + 1 \times 0 = 5 + 2 = 7~.
• Có thể chứng minh rằng đây là cách làm tối ưu nhất.