Mô tả đề bài

Alice và Bob là 1 cặp đôi yêu xa bởi Alice phải làm việc ở trong 1 khu rừng bí ẩn cách biệt với thành phố nơi mà Bob đang sinh sống. Hằng ngày Alice đều muốn gửi tới Bob những dòng tin nhắn đầy yêu thương, nhưng máy gửi tin của Alice đã bị hỏng do ngày ngày tháng tháng ở trong rừng, nhiều vi mạch đã bị chạm vì ẩm ướt. May thay, không phải máy truyền tin của Alice hoàn toàn không truyền tin được mà nó chỉ bị nhiễu trong quá trình truyền tín hiệu. Cơ chế của máy gửi tin mà Alice có là như sau:

• Khi Alice muốn gửi 1 từ là 1 chuỗi ký tự Alphabet thì Alice phải tự mình mã hóa chúng thành 1 chuỗi nhị phân gồm ~n~ chữ số 0 hoặc 1 rồi gửi cho máy gửi tin để phát sóng, biết máy gửi tin này có đúng n vị trí phát sóng.
• Máy gửi tin nhận được chuỗi ký tự nhị phân, nguyên tắc nếu không bị hỏng thì sẽ gửi tín hiệu đúng chuỗi nhị phân đó cho Bob. Tuy nhiên, vì máy gửi tin của Alice bị chạm nên một số bít trong chuỗi nhị phân sẽ không truyền được và mặc định sẽ truyền ký tự chữ số 0, cho dù bít đó thể là 0 hay là 1. Đương nhiên là Alice biết được vị trí bít bị trục trặc của máy truyền tin của mình trước khi truyền tin bằng một số cách thức nào đó.
• Sau khi gửi xong 1 chuỗi ký tự nào đó, vị trí bít bị trục trặc của máy gửi tin có thể bị thay đổi khi truyền chuỗi ký tự tiếp theo.

Bob, thì đương nhiên ở thành phố nên máy nhận tin của Bob sẽ không hề bị trục trặc như máy gửi tin của Alice. Vấn đề được đặt ra là khi nhận tin, Bob cần 1 đoạn code giải mã một cách hoàn hảo dòng tin nhắn của Alice cho dù các tín hiệu nhận được có bị thay đổi do máy gửi tin của Alice hay không. Vì thế Alice và Bob cần bạn mách bảo giúp cách thức mã hóa cho Alice và đoạn code giải mã cho Bob để họ có thể liên lạc với nhau 1 cách thuận tiện nhất. Yêu cầu, đoạn code giải mã phải được viết bằng Python không quá 1000 ký tự, không sử dụng bất kỳ thư viện nào và phải giải mã chính xác được tất cả các chuỗi ký tự mà Alice muốn gửi. Hãy giúp họ nhé!

Input format

• Dòng đầu là hai số nguyên ~m \; (1 \leq m \leq 1000)~ và ~n \; (1 \leq n \leq 200)~ lần lượt thể hiện số lượng chuỗi ký tự mà Alice muốn gửi và, số lượng vị trí phát sóng hay chiều dài chuỗi nhị phân mà Alice mã hóa.

• ~2 \times m~ dòng tiếp theo là các thông tin lúc Alice gửi các chuỗi ký tự alphabet, cụ thể như sau:

  • Dòng thứ ~2 \times i~ là chuỗi alphabet thứ ~i~ mà Alice muốn gửi. Chuỗi này có thể viết hoa hoặc viết thường, mỗi chuỗi không quá 10 ký tự.
  • Dòng thứ ~2 \times i + 1~ gồm các số nguyên dương thể hiện số lượng và vị trí bít bị trục trặc trong máy phát khi gửi chuỗi ký tự thứ ~i~. Số nguyên đầu tiên ~k_i~ là số lượng bít bị trục trặc, ~k_i~ số nguyên tiếp theo là các vị trí trục trặc ~x_{i,j}~. Biết, ~0 \leq k_i \leq n, \; 0 \leq k_i \leq 70~ và ~1 \leq x_{i,j} < x_{i, j+1} \leq n,\; 1 \leq j \leq k_i~.

    Ràng buộc

• Có 20% số testcase thỏa mãn với mọi ~k_i = 1~ và ~n = 120~.

• Có 20% số testcase thỏa mãn với mọi ~k_i \leq 2,\; n \geq 175~.
• Có 30% số testcase thỏa mãn với mọi ~2 < k_i \leq 40,\; n = 200~.
• Có 30% số testcase còn lại luôn thỏa mãn ~3 \times (k_i + 58) \leq 2 \times n~.

Output format

• ~m~ dòng đầu là các chuỗi nhị phân mà Alice mã hóa được từ các ký tự muốn gửi. Lưu ý, chuỗi nhị phân này có thể bị thay đổi như trong đề bài khi Bob nhận được.
• Các dòng tiếp theo là đoạn code giải mã dành cho Bob. Đoạn code này phải chứa hàm với tên là GiaiMa(x) được định nghĩa bởi ngôn ngữ lập trình Python với định dạng như sau, biết x là chuỗi nhị phân mà Bob nhận được và giá trị trả về là chuỗi ký tự sau khi giải mã

def GiaiMa(x):
    ...
  return ...

Biết ký tự tab có thể được thể hiện bằng 2 dấu cách.

Sample Input

3 120
I
0
Love
1 1
You
1 26

Sample Output

010001100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
010011000111101011000010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
011001100111101010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

def binToChar(binary):
    sum = 0
    for b in binary:
        sum = sum * 2 + ord(b) - ord('0')
    if sum == 0:
        return ''
    if sum <= 26:
        return chr(ord('a')+sum-1)
    if sum <= 52:
        return chr(ord('A')+sum-27)
def GiaiMa(x):
    i = 1
    s = ""
    while i <= len(x) - 6:
        s = s + str(binToChar(x[i:i+6]))
        i += 6
    return s

Giải thích ví dụ

Để ý trong testcase ví dụ, ta thấy trong tất cả quá trình gửi tín hiệu, chỉ có vị trí bít thứ 1 và bít thứ 26 bị trục trặc, vì thế Alice chỉ cần không sử dụng 2 bít đó để truyền thông tin là được. Vì số lượng chữ cái viết hoa và viết thường tối đa chỉ là 52 nên Alice chỉ cần sử dụng 6 bít để mã hóa cho mỗi ký tự:

• a: 000001
• ...
• z: 011010
• A: 011011
• ...
• Z: 110100

Đoạn code giải mã dựa vào cách thức mã hóa trên để giải mã.

Lưu ý, đoạn mã trong ví dụ chỉ giải quyết được đối với trường hợp đặc biệt của ví dụ này, nó không giải quyết được cho tất cả trường hợp của bài toán.