Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Tí và Tèo cùng đi du lịch sang một vương quốc nọ. Trước khi đi, 2 bạn đã phải đi đổi tiền và đã có được M đồng tiền trong tay. Điều đặc biệt ở vương quốc này đó là các đồng tiền có N mệnh giá khác nhau. Tuy nhiên, bề ngoài chúng lại có hình dạng và màu sắc giống hết nhau, chỉ khác nhau về khối lượng mà thôi. Khối lượng đồng tiền càng lớn thì giá trị của nó cũng càng lớn. N mệnh giá tương đương với các mức khối lượng K1, K2, ... KN (khối lượng tăng dần).

Không may thay, khi đổi tiền, Tí đã để lẫn lộn tất cả các đồng tiền với nhau, và bây giờ không biết làm cách nào để xác định được mệnh giá của đồng tiền. Hai bạn hiện tại chỉ có một chiếc cân thăng bằng trong tay. Do áp lực về mặt thời gian trước khi khởi hành, hai bạn chỉ có thể thực hiện được V phép cân.

Với mỗi phép cân, sẽ xác định được 2 đồng tiền có khối lượng bằng nhau hoặc khác nhau.

Nhiệm vụ của các bạn là hãy dựa vào bảng tổng kết các phép cân của Tí và Tèo, để xác định xem những đồng tiền nào có thể được xác định một cách chính xác mệnh giá của chúng?

Input

Dòng đầu tiên là số nguyên dương N, M, V (<= 300 000), tương ứng số mệnh giá các đồng tiền, số lượng đồng tiền đang có và số phép cân.

V dòng tiếp theo, mỗi dòng là một xâu có dạng AxB mô tả kết quả của phép cân thứ i. Trong đó, A, B là số thứ tự của đồng tiền được mang lên cân (A, B <= M). Kí tự x chỉ nhận giá trị “=” hoặc “<”. Phép cân cho biết đồng tiền thứ A có khối lượng bằng hay nhỏ hơn đồng tiền thứ B.

Output

In ra M dòng.

Dòng thứ i có dạng ‘KX’ trong đó X là một số nguyên có giá trị trong đoạn [1, N] nếu đồng tiền thứ i xác định được giá trị của nó và có giá trị nhỏ thứ X trong N mệnh giá, in ra “?” trong trường hợp ngược lại.

Example

Test 1:

Input:

3 5 3
1<2
2<4
3=5

Output:

K1
K2
?
K3
?

Giải thích test 1:

Đồng tiền 1 < 2 < 4. Do đó, đồng tiền 1 có mệnh giá nhỏ nhất, đồng tiền 2 có mệnh giá lớn thứ hai, đồng tiền 4 có mệnh giá cao nhất.

Hai đồng tiền thứ 3 và thứ 5 có khối lượng bằng nhau, nhưng không thể xác định được chính xác khối lượng của nó là lớn hay nhỏ thứ bao nhiêu.

Test 2:

Input:

2 7 6
1=2
2=3
2=7
3<4
4=5
4=6

Output:

K1
K1
K1
K2
K2
K2
K1