Tại Trường Đại học Quản lý và Công nghệ TP. Hồ Chí Minh, có một câu lạc bộ công nghệ trẻ trung mang tên GDSC-UMT. Đây là hội tụ nơi những sinh viên đam mê học hỏi, sáng tạo và cùng nhau khám phá thế giới công nghệ Google. Sau nhiều năm hoạt động, các thành viên mong muốn mở rộng định hướng phát triển. Vì vậy, Ban Chủ nhiệm quyết định thực hiện một cuộc hành trình đổi tên lịch sử: từ nay, CLB sẽ khoác lên mình diện mạo mới với tên gọi APC - Applied Programming Club.

Trước sự kiện này, mọi văn bản, tài liệu, bài đăng đều phải được chuyển đổi thương hiệu theo một số quy tắc nhất định:

• Google Developer Student Club → Applied Programming Club
• GDSC → APC

Yêu cầu

Hãy viết chương trình giúp Ban Chủ nhiệm CLB tự động chuẩn hoá toàn bộ văn bản cũ thành phiên bản mới.

Input Format

Vào từ thiết bị chuẩn có khuôn dạng:

• Dòng đầu chứa số nguyên ~N~ ~(1 ≤ N ≤ 100)~ — số dòng văn bản.
• ~N~ dòng tiếp theo, mỗi dòng là một chuỗi ký tự có độ dài không quá 255 ký tự.

Output Format

Ghi ra ~N~ dòng, mỗi dòng là kết quả sau khi đã thực hiện thay thế.

Ví dụ

Input

3
Google Developer Student Club
Cac ban GDSC rat nhiet tinh
Chao mung den voi GDSC!

Output

Applied Programming Club
Cac ban APC rat nhiet tinh
Chao mung den voi APC!

Ràng buộc

• Subtask 1 (50 điểm): Không có ký tự " " (khoảng trống).
• Subtask 2 (50 điểm): Không có ràng buộc nào thêm.

Trong buổi Bonding ra mắt CLB APC, để làm không khí thêm sôi nổi, Bruce – Phó Chủ nhiệm Thường trực – nảy ra ý tưởng về một trò chơi phân tích xâu ký tự.
Anh định nghĩa trọng số của một xâu ~S~ không rỗng như sau:

$$ \text{Trọng số}(S) = \frac{\text{số ký tự số trong } S}{\text{độ dài của } S} $$

Yêu cầu

Cho ~N~ xâu ~S_1, S_2, \ldots, S_N~ không rỗng, không chứa ký tự " " (khoảng trống).
Hãy tìm xâu có trọng số lớn nhất theo định nghĩa trên.
Nếu có nhiều xâu cùng trọng số lớn nhất thì chọn xâu xuất hiện sớm nhất trong danh sách.

Input Format

• Dòng đầu chứa số nguyên ~N~ ~(1 \le N \le 100)~ — số lượng xâu.
• ~N~ dòng tiếp theo, mỗi dòng chứa một xâu ~S~ (độ dài không quá ~1000~ ký tự).

Output Format

Ghi ra thiết bị chuẩn đúng một dòng — xâu có trọng số lớn nhất theo yêu cầu.

Ví dụ

Input

3
abc123
4567
apc2025

Output

4567

Ràng buộc

• Subtask 1 (100 điểm): Không có ràng buộc nào thêm.

Sau màn khởi động đầy sôi nổi cùng Bruce, Soraino – Phó Chủ nhiệm Chuyên môn – cũng muốn thử thách mọi người bằng một trò chơi mới.
Anh đưa ra một dãy số nguyên ~a_1~, ~a_2~, …, ~a_N~ và đặt câu hỏi:

"Hãy xóa đi đúng ~K~ phần tử trong dãy, sao cho số lượng giá trị phân biệt (tức các giá trị khác nhau) trong dãy còn lại là nhiều nhất có thể."

Yêu cầu

Tìm số lượng phần tử phân biệt lớn nhất có thể đạt được sau khi xóa ~K~ phần tử.

Dữ liệu vào

Vào từ thiết bị chuẩn:

• Dòng đầu chứa hai số nguyên ~N~, ~K~ ~(1 ≤ K < N ≤ 100000`)~
• Dòng thứ hai chứa ~N~ số nguyên ~a_1~, ~a_2~, …, ~a_N~ ~(|ai| ≤ 10^9)~

Dữ liệu ra

Ghi ra một số nguyên duy nhất — số lượng phần tử phân biệt lớn nhất còn lại sau khi xóa ~K~ phần tử.

Ví dụ

Input

7 3
5 7 5 5 1 2 2

Output

4

Giải thích:
Xóa 2 phần tử giá trị 5 và 1 phần tử giá trị 2.
Dãy còn lại có các số phân biệt: 5, 7, 1, 2 → tổng cộng 4 giá trị.

Giới hạn

• Subtask 1 (15 điểm): Mọi phần tử trong dãy đều phân biệt đôi một.
• Subtask 2 (15 điểm): ~K = 0~.
• Subtask 3 (70 điểm): Không có ràng buộc nào thêm.

Sau khi phải đau đầu với câu đố của Soraino, Bruce quyết định ra sân vận động để chạy bộ xả stress. Nhưng thay vì chạy quanh theo vòng tròn như mọi người, anh lại có một thói quen rất đặc biệt: chạy theo đường xoắn ốc hình vuông, bắt đầu từ chính giữa sân rồi xoắn dần ra ngoài theo chiều kim đồng hồ.

Sân vận động được mô tả dưới dạng một ma trận vuông kích thước ~N × N~ (trong đó ~N~ luôn là số lẻ). Bruce sẽ đánh số các bước chạy của mình từ 1 trở đi, và điền chúng vào ma trận theo đúng quy luật xoắn ốc:

• Bắt đầu từ ô trung tâm ~((N + 1) / 2, (N + 1) / 2)~.
• Bruce bắt đầu chạy sang phải, sau đó tiếp tục di chuyển theo chu kỳ 4 hướng: phải → xuống → trái → lên, lặp lại liên tục cho đến khi lấp đầy ma trận.
• Độ dài các đoạn di chuyển tăng dần tuân theo quy luật:
  • Hai đoạn đầu tiên dài 1 ô,
  • Hai đoạn tiếp theo dài 2 ô,
  • Hai đoạn tiếp theo dài 3 ô,
  • ...

Nói cách khác, độ dài các đoạn lần lượt là: 1, 1, 2, 2, 3, 3, 4, 4, …, kết hợp với chu kỳ hướng phải → xuống → trái → lên sẽ tạo thành quỹ đạo xoắn ốc mở rộng dần ra ngoài theo chiều kim đồng hồ.

Các số được đánh tuần tự 1, 2, 3, …

Tuy nhiên, trên sân có ~K~ ô được đặt chướng ngại vật. Khi Bruce đi qua một ô chướng ngại vật:

• Ô đó được điền số 0.
• Bruce "nhảy" qua chướng ngại vật đó, tiếp tục chạy theo quỹ đạo xoắn ốc.
• Số đếm vẫn tăng bình thường cho các ô tiếp theo không bị chướng ngại vật cản.

Ví dụ: với ~N = 5~, có ~K = 2~ chướng ngại vật tại các ô ~(3, 3)~ và ~(4, 3)~, kết quả thu được là:

$$ \begin{array}{ccccc} 19 & 20 & 21 & 22 & 23 \\ 18 & 5 & 6 & 7 & 8 \\ 17 & 4 & 0 & 1 & 9 \\ 16 & 3 & 0 & 2 & 10 \\ 15 & 14 & 13 & 12 & 11 \end{array} $$

Yêu cầu

Hãy viết chương trình mô phỏng lại quá trình chạy của Bruce.

Dữ liệu vào

Vào từ thiết bị chuẩn:

• Dòng đầu chứa hai số nguyên ~N~, ~K~ ~(1 ≤ N ≤ 999, 0 ≤ K ≤ N^2 - 1)~, trong đó ~N~ luôn là số lẻ.
• ~K~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x~, ~y~ ~(1 ≤ x, y ≤ N)~ — tọa độ của một ô có chướng ngại vật.

Dữ liệu ra

Ghi ra thiết bị chuẩn ma trận ~N × N~, mỗi ô chứa số thứ tự bước chạy hoặc 0 nếu là ô có chướng ngại vật.

Ví dụ

Input

3 0

Output

7 8 9
6 1 2
5 4 3

Giới hạn

• Subtask 1 (50 điểm): ~K = 0~.
• Subtask 2 (50 điểm): Không có ràng buộc nào thêm.

Câu lạc bộ APC luôn tin rằng xuất phát điểm không quyết định đích đến. Điều tạo nên sự khác biệt của một người không phải là việc họ bắt đầu từ đâu, mà là họ có đủ đam mê để theo đuổi con đường mình chọn hay không. Với niềm tin ấy, Groot – Chủ nhiệm APC - khởi xướng chương trình APC Olympic Mentoring - nơi mỗi thành viên đều có cơ hội phát triển và bứt phá thông qua huấn luyện lâu dài với sự đồng hành của các Mentor.

Mỗi thành viên trong APC sở hữu một chỉ số kỹ năng lập trình là một số nguyên dương. Trong chương trình, mỗi Mentor sẽ được ghép cặp với một Mentee phù hợp để hỗ trợ rèn luyện. Ta mô tả một cặp Mentor–Mentee bằng cặp số ~(x, y)~, trong đó:

• ~x~ là chỉ số kỹ năng của Mentor,
• ~y~ là chỉ số kỹ năng của Mentee.

Một cặp Mentor-Mentee được xem là hợp lệ nếu tồn tại một hành trình huấn luyện đủ dài để Mentee tăng trưởng đúng theo chuẩn của chương trình, tức là tồn tại số nguyên không âm ~n~ sao cho:

$$ \frac{y}{x} = k^n $$

Trong đó:

• ~k~ là hệ số phát triển kỹ năng - mô phỏng mức độ tiếp thu sau mỗi giai đoạn huấn luyện,
• ~n~ là số chu kỳ rèn luyện mà Mentee trải qua dưới sự dẫn dắt của Mentor.

Yêu cầu

Cho biết:

• Chỉ số kỹ năng của các Mentor thuộc đoạn ~[l_1, r_1]~,
• Chỉ số kỹ năng của các Mentee thuộc đoạn ~[l_2, r_2]~,
• Hệ số phát triển kỹ năng ~k~.

Hãy đếm số lượng cặp Mentor-Mentee hợp lệ.

Dữ liệu vào

• Dòng đầu là số nguyên ~t~ ~(1 ≤ t ≤ 10^4)~ - số lượng test.
• Mỗi test gồm 5 số nguyên ~k~, ~l_1~, ~r_1~, ~l_2~, ~r_2~ ~(2 ≤ k ≤ 10^9, 1 ≤ l_1 ≤ r_1 ≤ 10^9, 1 ≤ l_2 ≤ r_2 ≤ 10^9)~

Dữ liệu ra

Với mỗi test, in ra một số nguyên - số lượng cặp Mentor-Mentee hợp lệ.

Ví dụ

Input

5
2 2 6 2 12
2 1 1000000000 1 1000000000
3 5 7 15 63
1000000000 1 5 6 1000000000
15 17 78 2596 20914861

Output

12
1999999987
6
1
197

Giải thích:
Ở test case 1: với k = 2, các giá trị x trong đoạn [2, 6] có thể ghép với những giá trị y tương ứng trong đoạn [2, 12] sao cho y = x · 2^n.
Tổng số cặp thỏa điều kiện là 12.

Giới hạn

• Subtask 1 (30 điểm): ~k = 2~.
• Subtask 2 (20 điểm): ~t ≤ 20~, ~r1 - l_1 ≤ 2000~, ~r_2 - l_2 ≤ 2000~.
• Subtask 3 (50 điểm): Không có ràng buộc nào thêm.

APC Code Camp là hoạt động thường niên của APC - CLB Lập trình ứng dụng, nơi các thành viên vừa tham gia dã ngoại vừa rèn luyện kỹ năng lập trình qua các thử thách thực tế.
Khu vực tổ chức trại được mô phỏng dưới dạng một bản đồ với ~n~ khu vực, nối với nhau bởi ~m~ đường mòn hai chiều. Để đảm bảo an toàn liên lạc và vận chuyển nhu yếu phẩm giữa các nhóm, Ban Nhân sự muốn xác định những khu vực đóng vai trò ổn định trong mạng lưới, tức là những nơi không dễ bị cô lập khỏi phần còn lại của bản đồ.

Một khu vực được xem là an toàn nếu nó nằm trong một vùng mà tất cả các khu vực thuộc vùng đó đều có ít nhất hai đường mòn nối với những khu vực khác cũng thuộc vùng đó. Điều này bảo đảm rằng vùng vẫn duy trì được liên kết nội bộ ngay cả khi một đường mòn bị hỏng.

Lưu ý:

• Giữa hai khu vực không bao giờ tồn tại nhiều hơn một đường mòn trực tiếp.
• Không có đường mòn nào nối một khu vực với chính nó.

Yêu cầu

Hãy xác định số lượng khu vực thuộc vùng an toàn trong bản đồ.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên ~n~ và ~m~ ~(1 ≤ n ≤ 2 * 10^5, 0 ≤ m ≤ 2 * 10^5)~ – số khu vực và số đường mòn.
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~, ~v~ ~(1 ≤ u, v ≤ n, u \neq v)~ mô tả một đường mòn nối khu vực ~u~ và ~v~.

Dữ liệu ra

In ra một số nguyên duy nhất – số lượng khu vực thuộc vùng an toàn.

Ví dụ

Input

8 8
1 2
2 3
3 1
3 4
4 5
5 6
6 4
7 8

Output

6

Giới hạn

• Subtask 1 (10 điểm): Đồ thị là một cây.
• Subtask 2 (40 điểm): ~n ≤ 2000~, ~m ≤ 2000~
• Subtask 3 (50 điểm): Không có ràng buộc nào thêm.

APC - Applied Programming Club luôn lan tỏa tinh thần sáng tạo và nhiệt huyết đến cộng đồng sinh viên UMT.
Để kiểm tra mức độ "tình yêu" của bạn dành cho APC, hãy viết một chương trình thật đơn giản:

In ra dòng chữ:

I LOVE APC

Input

Không có input.

Output

In ra đúng duy nhất một dòng:

I LOVE APC