Cơ chế nhân đôi ADN diễn ra theo nguyên tắc bổ sung và bán bảo tồn. Nhờ đó, hai phân tử ADN con được tạo ra hoàn toàn giống nhau và giống với phân tử ADN mẹ. Cơ chế tự nhân đôi có ý nghĩa bảo đảm duy trì bộ NST đặc trưng của loài qua các thế hệ tế bào.

• Nguyên tắc bổ sung: Mạch mới của ADN con được tổng hợp dựa trên mạch khuôn của ADN mẹ. Các nucleotide ở mạch khuôn liên kết với các nucleotide tự do trong môi trường nội bào theo nguyên tắc A liên kết với T (bằng 2 liên kết hydro), G liên kết với X (bằng 3 liên kết hydro) hay ngược lại.
• Nguyên tắc bán bảo tồn: Trong mỗi ADN con có một mạch của ADN mẹ (mạch cũ), mạch còn lại được tổng hợp mới theo nguyên tắc bổ sung.

Trên đây là cơ chế nhân đôi ADN trong các dạng sống, sinh vật tại thế giới mà chúng ta đang sống. Nhưng tại Dị giới, tồn tại nhiều dạng sống vô định hơn, cơ chế di truyền của chúng cũng khác nhưng cũng có đôi chút giống với nơi chúng ta sống. Các dạng sống này tồn tại nhờ năng lượng của lõi vật chất gồm hai vùng vật chất liên kết với nhau. Chúng tăng số lượng bằng cách chia tách cơ thể, để đảm bảo tính di truyền với bản thể ban đầu thì lõi vật chất cũng phân tách, nhân đôi và cơ chế tương tự với cơ chế nhân đôi ADN. Nguyên tắc bán bảo tồn vẫn đúng trong trường hợp này, duy chỉ có Nguyên tắc bổ sung là có đôi phần khác vì lõi vật chất không chỉ cấu tạo dựa trên 4 loại nucleotide mà tổng cộng có 26 loại phân tử tương tự đánh số hiệu từ 'A' đến 'Z'. Theo như những nghiên cứu của những người đã lạc vào Dị giới trước đó, 26 loại phân tử này sẽ liên kết theo quy tắc gần tương tự Nguyên tắc bổ sung, với 13 cặp quy tắc. Với các quy tắc cho trước và một vật mẫu là 1 nửa lõi vật chất, để góp phần khôi phục phần nửa còn lại của mẫu vật hãy dự đoán cấu trúc của phần nửa còn thiếu của lõi vật chất

Nhập/ xuất qua file

Input : "notADN.INP"

Gồm ~13~ dòng mỗi dòng chứa ~1~ cặp ký tự thể hiện ~1~ cặp quy tắc (các cặp độc lập với nhau, mỗi ký tự xuất hiện tại đúng một cặp)

Dòng cuối gồm ~1~ xâu thể hiện cấu trúc phân tử của mẫu vật, 1 nửa của lõi vật chất.

(chỉ gồm các ký tự là chữ cái in hoa: 'A' -> 'Z')

Output : "notADN.OUT"

In ra cấu trúc phân tử dự đoán của nửa còn lại của mẫu vật.

Sample Input

A B
C D
E F
G H
I J
K L
M N
O P
Q R
S T
U V
W X
Y Z
LBELB

Sample Output

KAFKA

Subtask

• ~60\%~ số test có độ dài xâu thể hiện mẫu vật không quá ~10^5~
• ~40\%~ số test có độ dài xâu thể hiện mẫu vật không quá ~10^6~

Cho một tập hợp số nguyên gồm ~n~ phần tử. Hãy trả lời ~m~ truy vấn thuộc một trong hai loại sau:

• GREATER x : Hãy cho biết chỉ số của phần tử có giá trị lớn hơn ít nhất ~x%~ số lượng phần tử trong dãy, nếu có nhiều phần tử thỏa mãn in ra phần tử có chỉ số nhỏ nhất, nếu không tồn tại kết quả in ra -1.
• LESS x : Hãy cho biết chỉ số của phần tử có giá trị nhỏ hơn ít nhất ~x%~ số lượng phần tử trong dãy, nếu có nhiều phần tử thỏa mãn in ra phần tử có chỉ số lớn nhất, nếu không tồn tại kết quả in ra -1.

*Nhập/ xuất qua file

Input: "PERCENT.INP"

Dòng đầu tiên chứa số nguyên ~n~ số lượng phần tử của tập hợp ~(1 \le n \le 2.10^5)~

Dòng thứ hai gồm ~n~ số nguyên có trị tuyệt đối không quá ~10^9~, thể hiện tập hợp số nguyên.

Dòng đầu ba chứa số nguyên ~m~ số lượng truy vấn ~(1 \le n \le 2.10^5)~

~m~ dòng cuối mỗi dòng gồm ~1~ xâu thể hiện loại truy vấn và một số thập phân ~x~ có độ chính xác đến 6 số thập phân sau dấu "." ~(0 \le x \le 100)~

Output: "PERCENT.OUT"

Gồm ~m~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Sample Input

3
1 3 2
1
GREATER 33.3

Sample Output

2

Giải thích: phần tử thứ hai lớn hơn ~2/3~ số phần tử của mảng ~\approx 66,67%~, phần tử thứ ba lớn hơn ~1/3~ số phần tử của mảng ~\approx 33,33%~. Cả hai phần tử đều thỏa mãn truy vấn GREATER 33.3 nên ta xét phần tử có chỉ số bé nhất (ở đây là phần tử thứ 2).

Subtask

• ~50\%~ số test có ~n, m \le 1000~
• ~50\%~ số test còn lại không có điều kiện gì thêm

Bạn có một cây gậy dài, gồm m đoạn được đánh số từ ~1~ đến ~m~. Mỗi đoạn dài ~1~ cm. Tiếc là, một số đoạn bị hỏng và cần phải được sửa chữa.

Bạn có một cuộn băng dính dài vô tận. Bạn muốn cắt một số đoạn băng dính và dùng chúng để che tất cả các đoạn bị hỏng. Nói cách khác, một đoạn băng dính có độ dài ~t~ được đặt tại vị trí ~s~ nào đó thì chúng sẽ bao phủ các đoạn ~s, s + 1, …, s + t - 1~ của cây gậy.

Bạn được phép bao phủ cả những đoạn không bị hỏng, và các đoạn băng dính được phép chồng lên nhau.

Thời gian là vàng bạc, vì vậy bạn muốn cắt tối đa ~k~ đoạn băng dính liên tục để che tất cả các đoạn bị hỏng. Tổng chiều dài tối thiểu của những đoạn băng dính này là bao nhiêu?

Input: TAPE.INP

• Dòng đầu tiên: Gồm ba số nguyên dương ~n, m, k~ ~(1 \le n \le 10^5, n \le m \le 10^9, 1 \le k \le n)~ tương ứng với số đoạn bị hỏng, chiều dài của cây gậy và số đoạn băng dính tối đa bạn có thể sử dụng.
• Dòng thứ hai: Gồm ~n~ số nguyên dương ~b_1, b_2, ..., b_n~ ~(1 \le b_i \le m, 1 \le i\le n)~ tương ứng với các vị trí của các đoạn bị hỏng. Dữ liệu luôn đảm bảo bằng ~b_1 < b_2 < ... < b_n~.

Output: TAPE.OUT

• Gồm một số nguyên duy nhất là tổng độ dài tối thiếu của băng dính.

Sample Input 1

4 100 2
20 30 75 80

Sample Output 1

17

Sample Input 2

5 100 3
1 2 4 60 87

Sample Output 2

6

Subtask

• ~50\%~ số test có ~1 \le n \le 5000~
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Giải thích

• Ở test ví dụ thứ nhất, bạn có thể dùng một đoạn băng dính có độ dài ~11~ để che hai đoạn bị hỏng ~20~ và ~30~, một đoạn băng dính có độ dài là ~6~ để che hai đoạn bị hỏng ~75~ và ~80~, tổng độ dài là ~17~.
• Ở test ví dụ thứ hai, bạn có thể sử dụng một đoạn dài 4 để che các đoạn bị hỏng ~1~, ~2~ và ~4~, và hai đoạn có chiều dài ~1~ để che các đoạn bị hỏng ~60~ và ~87~.

Tại 1 vũ trụ nào đó, chuyến phiêu lưu tìm những viên ngọc rồng của nhóm chiến binh Z vẫn còn đang tiếp tục. Họ vẫn chưa thể tập hợp đủ các viên ngọc rồng bởi vì tại vũ trụ này rồng thần chỉ xuất hiện khi tập hợp đủ n viên ngọc rồng chứ không phải là 7 viên. Nhưng nhờ sự giúp đỡ của công nghệ radar tiên tiến, cuối cùng họ cũng sẽ tập hợp được tất cả chúng.

Bạn là vị thần sáng tạo nên biết vị trí của ~n~ viên ngọc rồng nằm trong vũ trụ này, tọa độ của chúng được biểu diễn bằng ~[x, y]~ trên mặt phẳng tọa độ ~Oxy~. Nhóm chiến binh Z có ~m~ người ở các vị trí khác nhau trên bản đồ và radar của họ có thể dò được những viên ngọc rồng có khoảng cách không quá ~r~. Với những chiếc radar đặc biệt này, cách chúng tính khoảng cách giữa ~2~ tọa độ ~[x, y]~ và ~[u, v]~ là ~max(|x - u|, |y - v|)~. Với mỗi chiến binh Z, hãy cho biết radar của họ dò được bao nhiêu viên ngọc rồng.

Input

Dòng đầu là ~3~ số ~n, m, r~ (~n, m \le 10^5; r \le 1000~).

~N~ dòng tiếp theo, dòng thứ ~i~ là vị trí ~[x_i, y_i]~ của viên ngọc rồng ~i~ sao (~x_i, y_i \le 5000~).

~M~ dòng cuối, dòng thứ ~i~ là vị trí ~[u_i, v_i]~ của người thứ ~i~ (~u_i, v_i \le 5000~).

Output

Gồm ~m~ dòng, dòng thứ ~i~ là số viên ngọc rồng mà người thứ ~i~ dò được.

Sample Input

4 1 7
6 7
5 13
10 15
9 8
14 8

Sample Output

2

Subtask

• ~50\%~ số test có ~m \le 100~;
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Note

Giải thích: Dò được viên ngọc ~3~ và ~4~.