Máy chủ nhận được một luồng dữ liệu là một xâu ký tự S siêu dài. Để tìm điểm bắt đầu của mã khóa, máy chủ cần tìm ra Ký tự đầu tiên (từ trái sang phải) KHÔNG BỊ LẶP LẠI trong toàn bộ xâu S. Nếu tất cả các ký tự đều bị lặp lại ít nhất 1 lần, hãy in ra dấu "#".

Input: Một dòng chứa xâu S (Độ dài <= 10^6).

Output: Ký tự thỏa mãn hoặc "#".

Ví dụ:

Input:

trungtamhoccongnghe

Output:

r

(Giải thích: Chữ t xuất hiện 2 lần. Chữ r xuất hiện 1 lần và nằm sớm nhất).

Trong một trò chơi sinh tồn, có N người chơi đứng tại các tọa độ Xi, và có N hầm trú ẩn tại các tọa độ Yj. Khi có còi báo động, mỗi người phải chạy ngay vào một hầm trú ẩn (mỗi hầm chỉ chứa đúng 1 người). Thời gian chạy tỷ lệ thuận với khoảng cách. Hãy sắp xếp phân công người vào hầm sao cho "người phải chạy xa nhất" có khoảng cách di chuyển là nhỏ nhất có thể.

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên Xi (-10^9 <= Xi <= 10^9).

Dòng 3: N số nguyên Yj (-10^9 <= Yj <= 10^9).

Output: Khoảng cách xa nhất phải chạy trong phương án tối ưu.

Ví dụ:

Input:

3
4 -4 2
4 0 5

Output:

4

(Giải thích: Xếp -4 vào 0 (cách 4), 2 vào 4 (cách 2), 4 vào 5 (cách 1). Xa nhất là 4).

File cấu hình cũ là xâu A, file cấu hình mới là xâu B. Hệ thống tự động chỉ hỗ trợ 2 thao tác: Chèn thêm 1 ký tự vào bất kỳ vào đâu hoặc Xóa đi 1 ký tự hiện có. (Không hỗ trợ thao tác Thay thế). Mỗi thao tác tốn 1 giây. Hãy tính số giây ít nhất để biến đổi xâu A trở thành xâu B.

Input:

Dòng 1: Xâu A (độ dài <= 2000).

Dòng 2: Xâu B (độ dài <= 2000).

Output: Số thao tác ít nhất.

Ví dụ:

Input:

heap
pea

Output:

3

(Giải thích: Xóa h (eap). Xóa p cuối (ea). Chèn p đầu (pea). Mất 3 giây).

Một chuỗi tín hiệu S bị rò rỉ, các hacker có thể lấy ra các "xâu con" (subsequence) của S bằng cách giữ nguyên thứ tự và xóa đi một vài ký tự. Hệ thống an ninh cần biết hacker có thể tạo ra tối đa bao nhiêu xâu con phân biệt (bao gồm cả xâu rỗng). Kết quả có thể rất lớn nên hãy in ra phần dư khi chia cho 10^9+7.

Input: Một dòng chứa xâu S chỉ gồm chữ cái in thường (Độ dài <= 10^5).

Output: Số xâu con phân biệt modulo 10^9+7.

Ví dụ:

Input:

aba

Output:

7

(Giải thích: Rỗng, a, b, ab, ba, aa, aba. Có tất cả 7 xâu).