#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <tuple>
#include <semaphore.h>
#include <pthread.h>
// #include <bitset> we won't use bitset due to variable length known at runtime
using namespace std;

vector<bool> numberToBinary(int number, int bitSize) {
  vector<bool> v(bitSize, false);

  for(size_t i = 0; i < bitSize; i++) {
    v[bitSize-i-1] = (number & (1<<i)) > 0;
  }

  return v;
}

string decToBinary(int bitSize, int currentCode) {
  vector<bool> v = numberToBinary(currentCode, bitSize);

  string s;

  for(size_t i = 0; i < bitSize; i++) {
    s += v[i]?"1":"0";
  }

  return s;
}

std::tuple<map<char,int>, vector<char>, vector<string>, int > readInput(int numCodes, int bitSize) {
  vector<string> message;
  map<char, int> codesIndex;
  char currentChar;
  int currentCode;
  string currentBinary;
  vector<char> charList;
  string tempLine;
  getline(cin, tempLine);
  int bitCount;
  int maxValue = 0;
  for(int i = 0; i < numCodes; i++) {
    getline(cin, tempLine);
    currentChar = tempLine[0];
    currentCode = stoi(tempLine.substr(2));
    if(currentCode > maxValue) {
      maxValue = currentCode;
    }
    codesIndex[currentChar] = currentCode;
    charList.push_back(currentChar);
  }

  bitCount = int(std::ceil(std::log2(maxValue)));

  string tempMessage;
  cin >> tempMessage;

  string tempString = "";
  int counter = 0;
  for(int i = 0; i < tempMessage.length(); i++) {
    if(counter == bitCount){
      counter = 0;
      message.push_back(tempString);
      tempString = "";
    }

    tempString += tempMessage[i];
    counter++;
  
  } 
  message.push_back(tempString);

  return std::tie(codesIndex, charList, message, bitCount);
}

struct code_s {
  char ch;
  string code;
};

struct thread_data_dec {
  vector<char> *output;
  vector<string> *input;
  vector<code_s> *codes;

  sem_t* msg_semaphore;
  
  int index;
};

void *decoding_thread(void *_arg) {
  thread_data_dec *arg = (thread_data_dec*)(_arg);

  auto msg = (*(arg->input))[arg->index];

  for(int i = 0; i < arg->codes->size(); i++) {
    code_s &cd = (*(arg->codes))[i];
    if(cd.code == msg) {
      (*(arg->output))[arg->index] = cd.ch;
    }
  }
  sem_post(arg->msg_semaphore);
  return nullptr;
}

struct thread_data_fc {
  code_s *code_struct;
  int charIndex;
  int bitCount;
  int frequency;
  vector<string> *message;
  sem_t *code_semaphore;
};

void *frequency_thread(void *_arg) {
  thread_data_fc *arg = (thread_data_fc*)(_arg);
  char currentChar = arg->code_struct->ch;

  auto &message = *arg->message;

  string code = decToBinary(arg->bitCount, arg->charIndex);

  int frequency = 0;

  for(int i = 0; i < message.size(); i++) {
    if(message[i] == code) {
      frequency += 1;
    }
  }	

  arg->code_struct->code = code;
  arg->frequency = frequency;

  auto sem = arg->code_semaphore;

  sem_post(sem);
  
  return nullptr;
}


int main() {
  int numCodes, bitSize;
  cin >> numCodes;
    
  auto [codesIndex, charList, message, bitCount] = readInput(numCodes, bitSize);
  vector<pthread_t> threads(numCodes);

  sem_t code_semaphore;

  sem_init(&code_semaphore, 0, 0);

  vector<code_s> codes(numCodes);

  vector<thread_data_fc> threadDataFc(numCodes);

  cout << "Alphabet:" << endl;
  { 
    int i = 0;

    for(auto &ch : charList) {
      codes[i] = {ch, ""};
      threadDataFc[i] = {&(codes[i]), codesIndex[ch],
	bitCount,
	-1,
	&message,
	&code_semaphore};
      pthread_create(&threads[i], NULL, frequency_thread, &(threadDataFc[i]));
      pthread_detach(threads[i]);
      i++;
    }
  }

  for(int i = 0; i < numCodes; i++) {
    sem_wait(&code_semaphore);
  }

  for(int i = 0; i < numCodes; i++) {
    cout << "Character: " << threadDataFc[i].code_struct->ch << ", Code: " << threadDataFc[i].code_struct->code << ", Frequency: " << threadDataFc[i].frequency << endl;
  }

  vector<thread_data_dec> threadDataDec(message.size());
  vector<char> output(message.size());
  threads.resize(message.size());

  for(int i = 0; i < message.size(); i++) {
    threadDataDec[i] = {&output, &message, &codes, &code_semaphore, i};
    pthread_create(&threads[i], NULL, decoding_thread, &(threadDataDec[i]));
  }

  cout << endl <<  "Decompressed message: ";

  for(int i = 0; i < message.size(); i++) {
    sem_wait(&code_semaphore);
  }

  string msg = string(output.begin(), output.end());

  cout << msg << endl;
}