DSA

Hospital Patient Queue Management

1.0 Task

Task: You are required to choose one of the following case studies. Once you’ve selected your case study, identify the problems it presents and propose a software solution using the C++ language that leverages the power of data structures. Your solution must include a project structure, dynamic arrays, functions, and classes. You may implement any of the Abstract Data Types (ADTs) for your solution. Each data type must include operations for adding, editing, deleting, and searching.

Case study: Hospital Patient Queue Management: Develop a system that manages the queue of patients in a hospital. Patient information can include patient ID, name, age, ailment, and time of arrival.

2.0 Some existing projects

  1. https://github.com/Abhiramborige/Library_Management-CPP/tree/master
    • 代码：使用3个class来管理整个系统，所有func都从class继承，没有例外，结构方面很好
    • Used: OOP, Files, RegEx, Array, Time
  2. https://github.com/islamapasss/LibrarySystem/tree/main
    • 很有趣的乱
    • 功能：可以很好的浏览不同的页面，比如"back"可以回到上一页
    • 学到了如何在不同dashboard之前返回和切换
  3. https://github.com/pawankumar1310/Library-Management-System
    • 不想看；# of .cpp files and .h files >= 20
  4. https://github.com/SaurabPoudel/lms
    • 不想看；# of .ccp files >= 10
  5. https://github.com/Rakshitgupta9/Library_Managment-CPP-PROJECT/tree/main
    • 为什么 admin_menu() 会 under BookOperation 的？你在干嘛？
    • 有 handle Ctrl+C event，程序崩溃也出不去 :(
  6. https://github.com/ayush-saklani/library-management-system
    • 代码：only function-prototype
    • 功能：前面讲到的功能都有 + 设计 + 自带数据库文件
    • 最完美的一个
  7. https://github.com/abdulsamie10/Library-Management-System
    • 什么都做的很好，就是没有 file handling

3.0 High-level overview

Tech stacks:

  • struct, class
  • linked list: node and queue
  • file handling: read and write text file

Important 4 parts:

  1. Helper functions: printColor(), generatePatientID(), getCurrentTime()
  2. Patient struct: id, name, age, ailment, arrivalTime
  3. PatientFileHandler class: getDelimeter(), appendToFile(), writeToFile(), readFromFile()
  4. PatientQueue class: enqueue, dequeue, edit, search, display, clear, about, exit

4.0 System implementation

4.1 Helper functions

void printColor(string text, string color); Print message in color
unsigned int generatePatientID(); Generates 4-digits numbers for Patient ID
time_t getCurrentTime(); Get the current time for Arrival Time

4.2 Patient struct

unsigned int id; Patient ID: random generated unique 4-digits positive number between 1000 and 9999
char name[30]; Patient name
unsigned int age; Patient age
char ailment[30]; Patient ailment
char arrivalTime[6]; Arrival Time: get from time library

4.3 PatientFileHandler class

  • char getDelimeter(); Get the delimeter for the text file
  • void appendToFile(); Append a patient to the text file
  • void writeToFile(); Write all patients to the text file
  • void readFromFile(); Read all patients from the text file (之后改成 patient * readFromFile())

4.4 PatientQueue class

  1. void enqueuePatient();

    • Task:
      • Add/Insert a patient to the queue
    • Requirements:
      1. Ask for id, name, age, ailment, arrival time, and then add to the queue
      2. For id, generate a unique 4-digits number OR ask user to input
      3. For arrival time, get the current time OR ask user to input
    • Conditions：
      1. Patient ID must be unique
      2. Patient ID must be in >=1000 & <=9999 numeric characters
      3. Patient name must not be empty AND <=30 characters
      4. Patient age must not be empty AND <=999 numeric characters
      5. Patient ailment must not be empty AND <=30 characters
      6. Arrival time must be in the format HH:MM
      7. Arrival time must not be empty AND <=5 characters

  2. void dequeuePatient();

    • Task:
      • Remove/Delete a patient from the queue
    • Requirements:
      1. Ask for patient ID, and then remove the patient from the queue.
      2. If patient ID not found, display a message
      3. Else, display a message say that patient removed
      4. Extra: display the patient information plus prompts confirmation before deleting
    • Conditions:
      1. Patient ID must be >=1000 & <=9999 numeric characters
    • Note:
      1. current one is based on patient ID, but can be based on other information such as index and name or combination, discussable

  3. void editPatient();

    • Task:
      • Edit/Update patient information
    • Requirements:
      1. Ask for patient ID
      2. If patient ID not found, display a message
      3. Else, display the patient information and ask for name, age, ailment, and arrival time
      4. For arrival time, get the current time or ask user to input
    • Conditions:
      1. Patient ID must be >=1000 & <=9999 numeric characters
      2. For conditions of name, age, ailment, and arrival time, refer to void enqueuePatient(), all the same
    • Note:
      1. current one cannot edit patient ID, which we expect the patient id is unchangeable during execution of program, discussable

  4. void searchPatient();

    • Task:
      • Search for a patient based on patient ID
    • Requirements:
      1. Ask for patient ID
      2. If not found, display a message
      3. Else, display the patient information
    • Conditions:
      1. Patient ID must be >=1000 & <=9999 numeric characters

  5. void displayPatients();

    • Task:
      • Display all patients in the queue, comes with index

  6. int promptMainMenu();

    • Task:
      • Print the main menu, comes with: enqueue, dequeue, edit, search, display, clear, about, exit

  7. void printAbout();

    • Task:
      • …no task, maybe remove this function in future.

5.0 Coding Template, can do reference

#include <iostream>
#include <iomanip>
#include <string.h>
#include <ctime>
#include <cstdlib>
#include <random>
// #include <string>
// #include <windows.h>
using namespace std;

//---------------------- Prototypes ----------------------//
void print(string text, string color);
unsigned int getRandomID();
char* getCurrentTime();

//------------------- Struct for patient information -------------------//
struct Patient {
    unsigned int id;
    char name[30];
    unsigned int age;
    char ailment[30];
    char arrivalTime[6];
    Patient* next;
};

//------------- Class for managing the queue of patients -------------//
class PatientQueue {
private:
    Patient* front;
    Patient* rear;
public:
    PatientQueue() {
        front = NULL;
        rear = NULL;
    }
    void enqueuePatient();
    void dequeuePatient();
    void editPatient();
    void searchPatient();
    void displayPatients();
    void clearScreen();
    int promptMainMenu();
    void printAbout();
};

//------------------------------------------------------------------------------------------------------------------//
//-------------------------------------- Function definations/implementations --------------------------------------//
//------------------------------------------------------------------------------------------------------------------//

//---------------------- Helper functions ----------------------//

/* Print messages with colors */
void print(string text, string color) {
    // 📝TODO
}

/* Generate a 4-digits random number between 1000 and 9999 */
unsigned int getRandomID() {
    // 📝TODO
}

/* Get current time in HH:MM format */
char* getCurrentTime() {
    // 📝TODO
}

//-------------------------------- Patient Queue functions --------------------------------//

/* [1] Add patient to queue */
void PatientQueue::enqueuePatient() {
    Patient* newPatient = new Patient;
    // 📝TODO
}

/* [2] Remove patient from queue based on patientID */
void PatientQueue::dequeuePatient() {
    // 📝TODO
}

/* [3] Edit patient information */
void PatientQueue::editPatient() {
    // 📝TODO
}

/* [4] Search for a patient in the queue */
void PatientQueue::searchPatient() {
    // 📝TODO
}

/* [5] Display all patients in queue */
void PatientQueue::displayPatients() {
    // 📝TODO
}

/* [6] Clear the console screen */
void PatientQueue::clearScreen() {
    // 📝TODO
}

/* Print the main menu and return the user's choice */
int PatientQueue::promptMainMenu() {
    // 📝TODO
}

/* [7] Print the about section */
void PatientQueue::printAbout() {
    // 📝TODO
}

//-----------------------------------------------------------------------------------------------------------//
//---------------------------------------------- Main function ----------------------------------------------//
//-----------------------------------------------------------------------------------------------------------//

int main() {
    PatientQueue queue;  //initialize the queue

    while (true) {
        int choice = queue.promptMainMenu();

        switch (choice) {
            case 1:
                queue.enqueuePatient(); break;
            case 2:
                queue.dequeuePatient(); break;
            case 3:
                queue.editPatient(); break;
            case 4:
                queue.searchPatient(); break;
            case 5:
                queue.displayPatients(); break;
            case 6:
                queue.clearScreen(); break;
            case 7:
                queue.printAbout(); break;
            case 8:
                cout << "space for testing stuff" << endl; break;  //debug purpose option
            case 0:
                cout << "> THANK YOU FOR USING THE SYSTEM!\n"; return 0;  //terminate the program
            default:
                // since the promptMainMenu() will handle invalid input, there no way user can reach here
                print("Unxpected error occured! Please try again", "red");
        }
    }
    return 0;
}

6.0 personal lastest coding

#include <iostream>
#include <iomanip>
#include <string.h>
#include <ctime>
#include <cstdlib>
#include <random>
#include <fstream>
#include <sstream>
// #include <string>
// #include <windows.h>
using namespace std;

//---------------------- Prototypes ----------------------//
void print(string text, string color);
unsigned int getRandomID();
char* getCurrentTime();

//------------------- Struct for patient information -------------------//
struct Patient {
    unsigned int id;
    char name[30];
    unsigned int age;
    char ailment[30];
    char arrivalTime[6];
    Patient* next;
};

//------------- Class for read/write patient records from/to a file -------------//
class PatientFileHandler {
private:
    const char d = ';';  //define delimiter here, better dont change it
public:
    char getDelimiter();
    void appendToFile(const string& filename, const Patient& patient);
    void writeToFile(const string& filename, Patient* front);
    Patient* readFromFile(const string& filename);
};

//------------- Class for managing the queue of patients -------------//
class PatientQueue {
private:
    Patient* front;
    Patient* rear;
    PatientFileHandler file;  //almost every method will access file
public:
    PatientQueue() {
        front = NULL;
        rear = NULL;
        loadPatientsFromFile();  //initialize the queue with data
    }
    void loadPatientsFromFile();
    void enqueuePatient();
    void dequeuePatient();
    void editPatient();
    void searchPatient();
    void displayPatients();
    void clearScreen();
    int promptMainMenu();
    void printAbout();
};

//------------------------------------------------------------------------------------------------------------------//
//-------------------------------------- Function definations/implementations --------------------------------------//
//------------------------------------------------------------------------------------------------------------------//

//---------------------- Helper functions ----------------------//

/* Print messages with colors */
void print(string text, string color) {
    if (color == "green") {
        cout << "\033[1;32m";
    } else if (color == "yellow") {
        cout << "\033[1;33m";
    } else if (color == "red") {
        cout << "\033[1;31m";
    }
    cout << text << "\033[0m" << endl;
}

/* Generate a 4-digits random number between 1000 and 9999 */
unsigned int getRandomID() {
    random_device rd;  //obtain a random number from hardware
    mt19937 eng(rd()); //seed the generator
    uniform_int_distribution<> distr(1000, 9999); //define the range

    return distr(eng); //generate and return the random number
}

/* Get current time in HH:MM format */
char* getCurrentTime() {
    time_t now = time(0);
    tm* ltm = localtime(&now);
    char* currentTime = new char[5];
    sprintf(currentTime, "%02d:%02d", ltm->tm_hour, ltm->tm_min);
    return currentTime;
}

//-------------------------------- File handling functions --------------------------------//

/* Get the delimiter used in the file */
char PatientFileHandler::getDelimiter() {
    return d;
}

/* Append patient data into a file */
void PatientFileHandler::appendToFile(const string& filename, const Patient& patient) {
    ofstream file(filename, ios::app);
    if (file.is_open()) {
        file << patient.id << d << patient.name << d << patient.age << d 
            << patient.ailment << d << patient.arrivalTime << endl;
        file.close();
    } else {
        cout << "Unable to open file: " << filename << endl;
    }
}

/* Overwrite patient data into a file */
void PatientFileHandler::writeToFile(const string& filename, Patient* front) {
    ofstream file(filename);  // overwrite mode
    if (file.is_open()) {
        Patient* temp = front;
        while (temp != nullptr) {
            file << temp->id << d << temp->name << d << temp->age << d << temp->ailment << d << temp->arrivalTime << endl;
            temp = temp->next;
        }
        file.close();
    } else {
        cout << "Unable to open file: " << filename << endl;
    }
}

/* Read patient data from a file in string format */
Patient* PatientFileHandler::readFromFile(const string& filename) {
    Patient* front = nullptr;
    Patient* rear = nullptr;
    string line;
    ifstream file(filename);
    if (file.is_open()) {
        while (getline(file, line)) {
            stringstream iss(line);
            string id, name, age, ailment, arrivalTime;
            getline(iss, id, d);
            getline(iss, name, d);
            getline(iss, age, d);
            getline(iss, ailment, d);
            getline(iss, arrivalTime, d);

            Patient* newPatient = new Patient;
            newPatient->id = stoi(id);
            strncpy(newPatient->name, name.c_str(), sizeof(newPatient->name));
            newPatient->age = stoi(age);
            strncpy(newPatient->ailment, ailment.c_str(), sizeof(newPatient->ailment));
            strncpy(newPatient->arrivalTime, arrivalTime.c_str(), sizeof(newPatient->arrivalTime));
            newPatient->next = nullptr;

            if (front == nullptr) {
                front = newPatient;
                rear = newPatient;
            } else {
                rear->next = newPatient;
                rear = newPatient;
            }
        }
        file.close();
    } else {
        cout << "Unable to open file: " << filename << endl;
    }
    return front;
}

//-------------------------------- Patient Queue functions --------------------------------//

/* Load patients from file to the queue */
void PatientQueue::loadPatientsFromFile() {
    front = file.readFromFile("patients.txt");
    if (front == nullptr) {
        print("> Alert: No data found in file.", "yellow");
        return;
    }

    // Find the last patient in the queue
    Patient* temp = front;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    rear = temp;
}

/* [1] Add patient to queue */
void PatientQueue::enqueuePatient() {
    Patient* newPatient = new Patient;

    cout << "Enter patient ID (leave empty for auto-generated ID): ";
    char input[5];
    cin.getline(input, 5);
    if (strlen(input) == 0) {
        newPatient->id = getRandomID();
    } else {
        newPatient->id = atoi(input);
    }

    cout << "Enter patient name: ";
    cin.getline(newPatient->name, 30);

    cout << "Enter patient age: ";
    cin >> newPatient->age;
    cin.ignore();

    cout << "Enter patient ailment: ";
    cin.getline(newPatient->ailment, 30);
    
    cout << "Enter patient arrival time (leave empty for current time): ";
    char arrivalTime[6];
    cin.getline(arrivalTime, 6);
    if (strlen(arrivalTime) == 0) {
        strcpy(newPatient->arrivalTime, getCurrentTime());
    } else {
        strcpy(newPatient->arrivalTime, arrivalTime);
    }

    newPatient->next = nullptr;

    if (front == nullptr) {
        front = newPatient;
        rear = newPatient;
    } else {
        rear->next = newPatient;
        rear = newPatient;
    }

    print("> Patient added to the queue successfully.", "green");

    file.appendToFile("patients.txt", *newPatient);  //update text file
}

/* [2] Remove patient from queue based on patientID */
void PatientQueue::dequeuePatient() {
    if (front == NULL) {
        print("> Queue is empty.", "red");
        return;
    }

    int id;
    cout << "Enter patient ID to remove: ";
    cin >> id;
    cin.ignore();
    cout << '\n';

    if (front->id == id) {
        Patient* temp = front;
        front = front->next;
        delete temp;
        print("> Patient removed from the queue successfully.", "green");
        return;
    }

    Patient* temp = front;
    while (temp->next != NULL && temp->next->id != id) {
        temp = temp->next;
    }

    if (temp->next == NULL) {
        print("> Patient not found in the queue.", "red");
    } else {
        Patient* toDelete = temp->next;
        temp->next = temp->next->next;
        delete toDelete;
        print("> Patient removed from the queue successfully.", "green");
    }

    file.writeToFile("patients.txt", front);  //update text file
}

/* [3] Edit patient information */
void PatientQueue::editPatient() {
    int id;
    cout << "Enter patient ID to edit: ";
    cin >> id;
    cin.ignore();
    cout << '\n';

    if (front != NULL) {
        Patient* temp = front;
        while (temp != NULL) {
            if (temp->id == id) {
                cout << "Enter new patient name: ";
                cin.getline(temp->name, 30);
                cout << "Enter new patient age: ";
                cin >> temp->age;
                cin.ignore();
                cout << "Enter new patient ailment: ";
                cin.getline(temp->ailment, 30);
                cout << "Enter new patient arrival time: ";
                cin.getline(temp->arrivalTime, 6);

                print("> Patient information updated successfully!", "green");

                file.writeToFile("patients.txt", front);  //update text file
                return;
            }
            temp = temp->next;
        }
    } 
    print("> Patient not found!", "red");
}

/* [4] Search for a patient in the queue */
void PatientQueue::searchPatient() {
    int id;
    cout << "Enter patient ID to search: ";
    cin >> id;
    cin.ignore();
    cout << '\n';

    if (front != NULL) {
        Patient* temp = front;
        while (temp != NULL) {
            if (temp->id == id) {
                cout << "Patient ID: "   << temp->id << endl;
                cout << "Name: "         << temp->name << endl;
                cout << "Ailment: "      << temp->ailment << endl;
                cout << "Arrival Time: " << temp->arrivalTime << endl;
                cout << "Age: "          << temp->age << endl;
                return;
            }
            temp = temp->next;
        }
    }
    print("> Patient not found!", "red");
}

/* [5] Display all patients in queue */
void PatientQueue::displayPatients() {
    if (front != NULL) {
        Patient* temp = front;
        int index = 1;

        cout << left;
        cout << "+---------------------------------------";
        cout << "----------------------------------------+" << endl;
        cout << "| No. | ID   | Name                 | Age";
        cout << " | Ailment              | Arrival Time |" << endl;
        cout << "+---------------------------------------";
        cout << "----------------------------------------+" << endl;
        while (temp != NULL) {
            cout << "| " << setw(3) << index++ << " ";
            cout << "| " << setw(4) << temp->id << " ";
            cout << "| " << setw(20) << temp->name << " ";
            cout << "| " << setw(3) << temp->age << " ";
            cout << "| " << setw(20) << temp->ailment << " ";
            cout << "| " << setw(12) << temp->arrivalTime << " ";
            cout << "|" << endl;
            temp = temp->next;
        }
        cout << "+---------------------------------------";
        cout << "----------------------------------------+" << endl;
    } else {
        print("> Queue is empty.", "red");
    }
}

/* [6] Clear the console screen */
void PatientQueue::clearScreen() {
    system("cls");
}

/* Print the main menu and return the user's choice */
int PatientQueue::promptMainMenu() {
    cout << '\n';
    cout << "------------------------------------------" << endl;
    cout << " Hospital Patient Queue Management System " << endl;
    cout << " [1] Enqueue Patient   [6] Clear Screen   " << endl;
    cout << " [2] Dequeue Patient   [7] About          " << endl;
    cout << " [3] Edit Patient      [8] Testing stuff  " << endl;
    cout << " [4] Search Patient    [0] Exit           " << endl;
    cout << " [5] Display Patients                     " << endl;
    cout << "------------------------------------------" << endl;

    int choice;
    do {
        cout << "> Enter your choice: ";
        cin >> choice;

        // check if the input was valid
        if (cin.fail() || choice < 0 || choice > 8 || (choice > 5 && choice < 6)) {
            cin.clear();  //clear the error state of the cin object
            cin.ignore(numeric_limits<streamsize>::max(), '\n');  //ignore rest of line
        } else {
            cin.ignore();
            break;  //if input valid
        }
    } while (true);

    cout << '\n';
    return choice;
}

/* [7] Print the about section */
void PatientQueue::printAbout() {
    cout << "Program name -> Hospital Patient Queue Management System (HPQM)" << endl;
    cout << "Description -> I love bocchi the rock so much" << endl;
    cout << "Version -> 1.0" << endl;
    cout << "Group members" << endl;
    cout << "    1. jiayi" << endl;
    cout << "    2. xiang" << endl;
    cout << "    3. seon" << endl;
    cout << "    4. alica i22023419" << endl;
}

//-----------------------------------------------------------------------------------------------------------//
//---------------------------------------------- Main function ----------------------------------------------//
//-----------------------------------------------------------------------------------------------------------//

int main() {
    PatientQueue queue;  //initialize the queue

    while (true) {
        int choice = queue.promptMainMenu();

        switch (choice) {
            case 1:
                queue.enqueuePatient(); break;
            case 2:
                queue.dequeuePatient(); break;
            case 3:
                queue.editPatient(); break;
            case 4:
                queue.searchPatient(); break;
            case 5:
                queue.displayPatients(); break;
            case 6:
                queue.clearScreen(); break;
            case 7:
                queue.printAbout(); break;
            case 8:
                cout << "space for testing stuff" << endl; break;  //debug purpose option
            case 0:
                cout << "> THANK YOU FOR USING THE SYSTEM!\n"; return 0;  //terminate the program
            default:
                // since the promptMainMenu() will handle invalid input, there no way user can reach here
                print("Unxpected error occured! Please try again", "red");
        }
    }
    return 0;
}

i m crazy

/* Print exit message */
void PatientQueue::printExitMessage()
{
    system("chcp 65001 > nul && cls");
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣟⣻⡿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣛⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣷⢿⡹⣜⢛⡞⣭⢿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⣫⣷⣳⡓⣟⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣯⢶⣞⢫⠞⡬⡓⢯⡺⡽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⣿⣿⠿⣋⠷⡹⣅⣳⣥⢟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⡿⣿⣻⣿⣻⣿⣯⢿⡶⣹⢱⣙⢮⡱⣏⢷⡿⣽⣻⢿⠿⣹⠣⡙⠎⠛⡉⢉⠙⡉⢋⠁⠉⠀⠉⠩⠁⠔⡨⢍⡍⢻⢍⢇⡻⢌⡳⠵⢯⣷⢟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣟⣿⢿⣿⣽⡿⣽⣿⣯⠿⣥⢫⣜⣲⠹⣎⠷⣛⢖⡩⢎⠱⣂⠳⡅⠌⠁⡐⠀⢂⠈⠀⠀⠀⠀⡈⠠⠐⣀⠳⢢⠌⠣⢌⠦⡱⢩⡑⢯⢻⢽⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⢿⣹⣿⣾⣏⣿⢿⡾⣿⣿⢉⡷⣎⢶⠹⣆⠹⡰⢎⠱⢎⠱⡈⢱⠆⠰⠀⡀⠀⠀⠀⠀⠀⠀⠆⡰⢁⠶⣀⠉⡆⡈⠱⠎⣆⠱⢇⡎⢇⠏⡾⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⡿⣯⣷⣿⡾⣽⣯⣿⡷⣿⣷⡜⡌⢣⠱⢌⠱⡑⡌⡚⢌⢆⣉⡆⡐⢂⠡⠀⠁⠀⠀⢀⠀⠌⡠⡑⢎⠲⢤⠓⡴⢡⢋⡼⢰⡙⢦⡘⣌⠺⣱⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣽⣷⣻⢾⣽⣻⣞⡷⣿⣷⣟⡂⠜⡠⢉⠆⣵⣴⣾⣷⣾⣾⣷⣾⣔⡉⠀⠀⠀⠀⠁⠠⠈⠤⠑⡸⢌⠓⣬⣻⣼⣿⣿⣿⣿⣿⡶⠿⣬⠳⣍⢾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣳⣟⡿⣿⣾⣳⢯⣿⣽⣞⢯⢉⠆⣁⢊⠰⠀⠌⠛⠛⠛⠟⠻⠛⠻⡧⠀⠀⠀⠀⠀⠄⠡⢀⠡⠐⢨⠘⠼⠟⠛⠛⠛⠛⠉⠁⢂⠅⢢⠙⣌⢲⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⡷⣯⢾⡽⣏⡿⣽⢯⣿⠾⡟⠡⠌⡂⠔⠀⡀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⡀⠄⠠⡀⢆⠠⢄⡩⠄⡌⠄⠂⠈⠀⢀⠀⡐⢄⠂⣌⢢⡙⣬⢯⣳⢯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⡿⣽⡳⢿⣹⡽⢯⡿⣽⣻⡄⢃⠒⡐⠌⡰⠀⠂⠤⠀⠀⠀⠀⠀⠀⠀⠀⠀⡐⢐⣸⣳⡜⣬⣳⢦⣷⣹⡰⠀⠂⢄⠡⠐⡠⢌⠢⡙⣆⡧⣝⠮⢯⡽⠾⣿⡿⣿⣿⣿⣿⣿⢿⣿⣿\n";
    // cout << "⡿⣵⣻⢯⢷⣻⢯⣿⠾⣵⡟⡄⠣⠌⡱⢠⢋⡝⠤⢁⠈⠀⠄⠀⡀⢀⠠⠐⠈⠻⣶⣷⣿⣷⣯⣿⣿⠿⡣⣍⡘⢄⢢⢡⡐⡌⡒⢷⡶⣾⢻⣿⣻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⡟⣧⣛⡾⣭⣭⢯⣷⣟⣶⣻⢧⡑⣊⠔⢣⠏⣜⡓⠆⡐⠁⢂⠐⠠⠂⡔⣈⠲⣩⢞⣿⣿⣿⣿⡿⣋⡳⡱⢎⡞⣌⢓⣢⣱⣤⣭⢶⣶⢷⣷⣯⣭⣯⣽⣿⣿⣿⣟⣿⣿⣿⢿⣿⣿\n";
    // cout << "⣟⢷⣫⢟⣳⣏⠿⣿⣻⢮⣽⣯⢼⡐⠎⡌⠻⣌⡹⢦⡱⢈⡃⠜⡡⢳⡔⢮⣝⣷⡿⣾⣿⣿⣟⡶⢧⣷⢿⣟⡾⣭⣏⣳⣭⣓⢿⡿⣾⣿⣭⣶⣛⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣏⣷⣫⣿⣶⣿⣿⣽⣟⣯⣷⣾⣿⡄⠂⠌⢓⠲⢍⢖⡡⢏⡼⣹⣝⢯⣾⣿⣾⣾⣿⣷⣿⣿⣿⣿⣿⣾⣿⣾⣿⣿⣻⡿⣮⣻⢷⣽⣻⢾⣽⢯⣿⣿⣿⣷⣾⣯⣟⣿⢿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣟⣯⣗⡂⠁⠌⡀⠎⠒⡌⢲⡉⢖⡱⢎⡿⢾⣿⡟⡯⢹⡹⣭⢟⡼⢣⢟⣽⢫⣿⣿⣿⣿⣽⣷⣿⣟⣽⢟⣷⣮⣟⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣻\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣿⣽⣾⣿⣿⣿⠃⢈⠐⡀⠃⡜⠰⢣⢜⡣⣝⢮⡹⣏⢾⡛⣴⢯⣵⢋⡷⣍⠞⣮⠱⡳⢾⣿⣟⣾⣿⣯⣿⣾⢯⡿⣵⢾⡽⣿⣾⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⡏⠀⢂⠐⠠⠡⢠⠙⢢⡙⢮⡹⢶⡽⣎⣷⣙⢶⣫⡞⣯⣶⡝⡞⡜⢡⣛⣯⣿⣿⣿⣿⣽⣟⣿⢯⡷⢯⡷⣽⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠗⠈⠀⢈⠡⡘⢄⡉⢆⡙⢦⡙⢮⢱⡻⢶⣛⡮⣖⢿⡽⣞⣯⣗⣧⡔⣣⣿⣿⣿⣻⣽⡿⣞⣯⢿⡽⢯⣝⢯⣞⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠀⠀⠂⠑⢀⠢⢘⠠⡑⢢⠘⠤⢃⠞⣣⢻⡵⣯⣟⣾⣽⣳⡿⣝⣿⣽⣿⣿⣻⣽⡷⣟⣯⣟⣯⡽⣏⢞⡳⣞⡼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠀⠀⠀⠀⢀⠰⠈⠰⡀⢁⠎⢁⢇⠸⡰⢏⢷⣹⢾⣷⣏⣿⣹⡿⣾⣏⣷⣿⣹⣾⣹⣏⣷⢿⣸⢷⡹⣎⢷⢱⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⡀⠀⠀⠀⢈⠐⠠⢁⡘⠤⢊⠴⣡⢋⠾⣱⢟⡾⣽⢾⣽⣻⣽⢯⣷⢯⡷⣯⢷⡻⣞⢯⡞⣧⡝⡮⣝⢎⡯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠄⢂⠀⡐⠀⠄⠂⢀⠁⢂⠐⡠⢃⠲⢄⡫⣚⢵⢫⠾⣝⡿⣞⣯⣟⡿⣞⣯⢿⣹⠾⣝⡯⣞⡽⣲⠽⣱⢎⡳⣞⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠌⠠⠐⡀⠌⡀⠄⡀⢢⠐⢨⠐⡡⢊⢦⠱⣩⠞⣭⠻⣭⢻⡽⣾⣽⣻⡽⣯⢿⣭⢿⣹⢞⡵⣫⢇⡻⣥⠯⣝⡽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠆⠡⢈⠐⠠⠈⢄⡁⠆⡘⢄⢊⠱⣈⠆⠳⡄⢫⠔⣋⠖⣫⢗⣳⣞⣷⣻⣽⣻⢾⡭⣗⢯⢺⢥⣫⢳⡕⣫⣜⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⡐⠠⠈⠄⡑⠠⠐⠠⠌⠂⡌⠑⠠⠌⡑⠨⢐⠨⢐⡋⢖⡩⢶⡹⣞⡷⣯⣟⡿⣼⡹⣎⢯⢖⡭⣖⣫⢵⡾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⢈⡐⠡⢀⠐⠀⢀⠀⠁⡀⠁⠂⠄⠁⠂⠄⢂⠡⠘⢤⠙⢆⡻⢼⡝⡷⢯⣟⣞⣳⡽⣎⡟⣖⢧⣛⡾⡽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    // cout << "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠆⢌⠂⣄⠂⠌⡀⢂⠡⢀⠀⠁⠀⠌⠀⡐⠀⢂⠉⢆⡘⠤⠙⣆⢫⡽⣛⣮⣟⣧⣟⣳⠿⣜⣻⢮⣟⣵⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n";
    
    cout << "⠀⠀⠀⢎⣰⡡⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⡀⠄⠀⠀⡜⠡⡀⠤⢀⡐⣠⡤⠲⠤⠐⢶⣬⣳⡄⠀⠀⠀⠀⢱⣂⣒⡼⠃⠀⠀⠀⠸⢄⣣⣆⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⠀⠀⠀⠀⠀⠀⠄⠠⠀⠀⠀⠀\n";
    cout << "⠀⠀⠀⠈⠁⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡜⠠⡁⣐⠴⠊⠁⠁⠀⠀⠀⠀⠈⠀⠈⠙⣦⠀⠀⠀⠀⠉⠉⠀⠀⠀⠀⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀\n";
    cout << "⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣁⡖⠚⠁⠀⠀⠀⠀⢀⠀⣀⠠⠤⠤⠀⠒⠒⠒⠒⠒⠀⠠⠤⠤⢀⣀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀\n";
    cout << "⠀⡀⢄⢦⡀⠀⠀⠀⠀⣠⠖⠶⣄⠀⠀⠀⠀⠀⠄⠀⠠⡀⠀⠀⡾⠈⡠⠂⢰⡀⡄⠆⠃⢈⣁⠠⡤⠀⠴⠠⡀⠄⣀⠠⢀⠠⢐⠒⠶⠢⠠⢬⢁⡘⠰⠠⢄⡀⠀⠀⣠⠶⢲⣄⠀⠀⠀⠀⠀⡄⠂⠦⡀⠀⠀⠀⠀⢠⠔⠰⢄⠀⠀⠀⠀⠀\n";
    cout << "⠠⢉⢆⢢⡷⠀⠀⠀⠀⣇⢎⡱⣸⠆⠀⠀⠀⠈⠀⢀⠀⡱⠀⠀⠀⠀⡣⠖⠉⣀⠤⠒⠩⢁⠂⡐⠄⠡⢂⠑⡐⠂⢄⢂⠂⠒⣀⠊⠄⠡⠈⠄⠂⠌⡑⠢⢄⡈⠑⠄⣧⢊⡵⣸⠇⠀⠀⠀⠸⢀⣠⠠⠍⡀⠀⠀⠀⣇⠠⠀⣈⠇⠀⠀⠀⠀\n";
    cout << "⠀⠈⠀⠋⠀⠀⠀⠀⠀⠈⠃⠙⠉⠀⠀⠀⠀⠀⠙⠀⠋⠁⠀⢠⠔⢈⣠⠞⠉⠄⢂⢁⠒⡀⠒⠠⠌⡁⠆⠌⡄⠩⣀⢂⠩⠐⠄⢊⠌⠡⠑⡈⠌⡐⠠⢁⠂⡉⠓⢤⡈⠙⢖⠉⠀⠀⠀⡴⠘⠉⣀⢠⠄⡈⠱⡀⠀⠈⠃⠈⠉⠀⠀⠀⠀⠀\n";
    cout << "⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⠜⢁⡴⠃⠄⢂⠡⠈⡄⠢⠌⣰⠃⡅⠂⢌⠐⠡⣀⠃⢄⠂⢂⠉⡐⢂⠌⣀⠃⠰⡐⠠⣁⠂⠆⠡⣌⠠⢉⠳⢎⣁⠙⠔⠁⣠⠔⠩⠐⠂⠌⠱⡄⢩⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀\n";
    cout << "⠀⠀⠀⠀⢠⠀⠀⠀⠀⠀⣀⠴⠆⣄⠀⠀⢀⢠⠰⣒⡥⢁⡴⢫⡝⢨⠐⣦⢁⠃⣤⡁⢢⡇⠱⢀⠡⠂⢌⠐⠠⠌⠂⡌⠠⠘⠠⢈⠰⢀⡘⢰⠀⢳⠆⣈⠂⠡⠌⠇⢂⡾⢁⠈⣷⠒⢊⠡⢈⡐⠡⠉⡌⢄⠳⠈⡄⠀⢀⡤⢠⣄⠀⠀⠀⠀\n";
    cout << "⠀⠀⠀⢀⠀⡁⠀⠀⠀⠀⡇⢠⠤⢜⠂⠉⠀⠀⢸⠅⣠⠋⠄⠛⢠⠁⣼⠃⢄⢺⡰⣰⣟⠠⠑⡨⢀⣿⠌⡰⢁⠂⠡⢀⠡⢃⠡⢄⠂⠆⠠⢃⡇⢂⢻⡀⡘⠄⠚⡈⢸⡅⢂⢂⣸⠇⢂⠐⠤⢀⠃⠤⢘⠠⢸⠇⡇⠀⡇⠀⠄⢸⠄⠀⠀⠀\n";
    cout << "⠀⠀⠀⠀⠐⠁⠀⠀⠀⠀⠑⠶⠆⠋⠀⠀⠀⢠⠃⣜⠂⢌⠠⡁⠆⡐⡎⡐⠈⡄⢰⣃⣯⠆⡑⠠⣜⠂⣇⠰⢀⠡⢂⡁⠒⠰⠶⠶⢬⡴⣁⡢⠐⢂⠸⡅⡐⢈⠄⢡⠂⣹⠆⢲⣇⠨⠄⢊⠐⠂⠌⢠⠁⢂⠌⡀⡇⠀⠘⠣⠖⠋⠀⠀⠀⠀\n";
    cout << "⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠃⢬⠁⠌⢂⠰⢐⡐⣼⠁⢄⡣⢞⠋⢠⠆⡐⠨⢰⡏⠀⢹⡐⠄⢂⡐⢠⠉⡔⡀⠆⢸⣇⢈⠉⠓⠦⣆⢳⠈⡄⠈⠆⣸⠃⠌⠄⣸⡆⠌⡀⠎⠰⡈⠤⠈⢄⠂⠄⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀\n";
    cout << "⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠇⢠⡇⠌⢂⡿⠈⠤⣰⢹⡼⠋⣐⡎⠀⢠⣃⠄⢃⣶⠀⠀⠀⢳⡌⡐⠠⠙⣧⡐⠠⠃⡄⢿⡆⢉⡐⢂⡘⢹⡐⠄⡉⡐⠘⣧⣈⣔⡞⢀⠂⠔⣈⠡⡐⠌⡁⠂⢌⠠⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀\n";
    cout << "⠀⠀⠀⠀⠀⢀⠄⠠⡀⠀⠀⠀⠀⠀⡤⢺⡄⡜⡇⢈⠂⣧⠘⡀⣏⢸⡀⠆⣼⠀⠀⠀⡿⠐⢠⡇⠀⠐⠀⠈⢳⡄⢃⠁⠿⢳⡁⠂⠔⠸⡛⣤⠐⡠⠐⡈⣇⠂⠔⡈⠡⢠⡿⣏⢀⠂⠌⡐⠄⠒⡠⠊⢄⠡⢂⠂⠄⠀⠀⠀⠀⠀⣠⠲⢠⡀\n";
    cout << "⠄⠀⠀⠀⠀⡁⠀⠀⢸⠀⠀⠀⠀⢸⠀⢸⠄⡇⡇⠌⡐⣿⡐⢠⡏⠀⣇⢰⡋⠀⣀⣄⣸⠇⣸⠁⠀⠌⠀⠁⠀⠙⢦⠁⡸⡇⠙⢦⡁⠆⢫⣈⣦⡁⠆⡁⡧⢈⡐⠠⠃⣌⠻⣇⡠⠌⡐⠠⢉⡐⠡⠘⣀⠂⠔⡈⢸⠀⠀⠀⠀⢸⣀⠃⠆⡴\n";
    cout << "⠀⠀⠀⠀⠀⠈⠐⠀⠀⠀⠀⠀⠀⠈⠑⠞⢇⡇⢳⠈⠄⣿⢧⠸⣇⠀⣹⣼⣷⠿⠛⢿⣿⣿⣸⡀⠄⠠⠈⠐⢀⠀⠈⠳⢤⣻⣴⡿⠟⢮⡙⡿⣿⣿⣦⠐⡇⠤⢀⠑⠂⣽⠀⠌⡙⡇⢠⠁⢂⠄⢃⠡⠄⡘⠠⠄⡁⠀⠀⠀⠀⠀⠁⠞⠊⠀\n";
    cout << "⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠈⢧⡈⢿⣚⣷⡷⣴⣿⠟⠀⠀⠀⠀⣿⣿⣿⣷⠀⠠⠀⡁⠀⠂⠠⠀⢰⣿⣿⠁⠀⠀⠉⠺⣹⣿⣿⣷⣸⠐⡀⢊⡁⢾⠈⡐⢠⣿⠀⠌⠄⡊⠤⢁⠊⠄⡑⠠⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀\n";
    cout << "⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠓⣜⣷⢺⣷⣿⣿⣦⣀⣀⣠⣼⣿⣿⣿⣿⠀⠐⠀⠄⠁⠄⠁⢈⣿⣿⣿⣦⣀⣀⣠⣴⣿⣿⣿⣿⡏⠰⢀⠡⡀⢿⣰⠧⣼⢿⢈⡐⢈⠰⢀⠃⠌⡐⢈⠄⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀\n";
    cout << "⠀⠀⠀⠀⠀⢠⠚⢉⠲⡀⠀⠀⠀⢀⡴⢋⡑⢦⠀⠀⠀⡇⢹⣟⣿⣿⣿⣿⡿⠛⢿⣿⣏⣹⣿⡟⠀⠈⠄⠈⡀⠂⢈⠀⢹⣿⣿⡏⠁⢙⣿⣿⢋⣿⣿⣿⡇⠱⡀⠁⠆⣿⢯⠿⣭⣿⡄⠐⣀⠊⢄⠊⠔⠠⢁⠂⡷⡄⠀⠀⠀⠀⡴⢩⢍⡢\n";
    cout << "⠀⠀⠀⠀⠀⢳⡈⠄⣢⠇⠀⠀⠀⠘⣆⠢⢘⡼⠀⠀⠀⠇⢠⠉⣷⠹⣿⣿⣷⣶⣿⣿⣿⠿⠋⠀⢀⠡⠀⢂⠀⠌⠀⡀⠀⠙⠻⢿⣿⣿⣿⣿⣿⠿⠿⠋⡧⠡⠐⡉⠄⣿⠾⠻⡶⢣⡇⠡⢀⠌⢂⠌⠂⡅⠊⠄⣷⠇⠀⠀⠀⠈⢇⡣⢎⡰\n";
    cout << "⠀⠀⠀⠀⠀⠀⠈⠉⠀⠀⠀⠀⠀⠀⠀⠉⠉⠀⠀⠀⠀⢸⠠⢈⡷⠀⠀⠉⠉⠉⠁⡀⠀⡀⠄⠐⠀⠠⠐⠀⡀⠂⠐⠀⡐⠀⡀⠀⠀⠀⠁⠈⢆⣀⡰⢸⠇⠡⢁⡘⢀⠯⠀⠀⠸⡄⣃⢁⠂⠌⢂⠌⠡⡀⠥⠈⡇⠀⠀⠀⠀⠀⠀⠉⠉⠀\n";
    cout << "⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠠⢹⡇⠀⢀⠂⠁⠈⢀⠠⠐⠀⡀⠂⠈⠀⠀⠄⠀⡀⠁⢀⠠⠐⠀⠄⠁⡈⠠⠁⠀⢀⣀⢸⣀⠣⠀⡔⢈⡆⠐⠀⢘⠇⢽⠠⢈⠐⠡⡈⠅⡐⠠⠃⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀\n";
    cout << "⠀⠀⠀⠀⠀⢀⣀⡀⠀⠀⠀⠀⠀⠀⣀⣀⠀⠀⠀⠀⠀⠘⡄⣿⠀⠀⢀⠠⠈⠐⡀⠄⠐⡀⢀⢀⡶⣛⠹⠳⣄⣀⣐⡀⠀⠠⠁⡈⠄⠠⠐⠈⣰⠋⠈⡿⢀⠂⢡⠐⢨⡇⠀⠈⡸⢀⣨⡔⢀⠊⢡⠐⠌⠠⠑⡈⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀\n";
    cout << "⠀⠀⠀⠀⢰⠋⡄⢊⣇⠀⠀⠀⠀⡞⡡⢎⢳⡄⠀⠀⠀⢰⣇⠹⣄⡀⠀⡀⠀⠁⠀⠄⠂⠀⠄⢸⡧⢌⢃⠳⡘⢤⢃⡿⠀⠐⠠⠀⢀⠂⠠⠀⠱⣄⣠⡇⠢⠌⡀⠎⢸⣁⠤⠞⡝⡱⢸⠇⠂⠌⡀⠎⣀⠃⠌⡐⡇⠀⠀⠀⠀⡔⠁⠀⠀⠀\n";
    cout << "⠀⠀⠀⠀⠈⠶⣈⠶⠋⠀⠀⠀⠀⠳⢅⡮⠞⠁⠀⠀⠀⠘⠾⡀⠄⡙⠲⢤⣁⡀⠂⢀⠈⠀⢀⠻⣔⢊⡬⢡⡙⢤⡛⠁⠀⠐⠀⡈⠀⠀⢀⡤⠖⠊⢁⢃⢁⠂⠌⠄⡛⠀⠀⠀⠓⢵⡬⡟⢈⡐⠐⠌⢄⡈⠔⡀⡇⠀⠀⠀⠀⠐⠤⠈⠀⠀\n";
    cout << "⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⣇⣿⢀⠡⢸⠇⠈⠑⠒⠰⠎⢠⣤⣈⠁⠈⠓⣚⠃⣀⢤⡈⠀⠄⣠⠶⠛⠉⠀⠀⠀⠸⢂⢂⣾⠋⢰⠃⠀⠀⠀⠀⠀⠀⢸⠄⡄⠃⠌⡄⡐⠄⢂⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀\n";
    cout << "⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⣬⢣⡐⠘⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡤⠜⠛⣍⢲⠏⠀⠀⡗⠂⠤⢄⠀⠀⠀⠟⠠⡜⡝⢠⠏⠀⠀⠀⠀⠀⠀⠀⠀⡇⠤⢁⠢⢐⠠⠘⡀⠆⠀⠀⠀⠀⠀⠀⠀⠀⠀\n";
    cout << "⡀⠀⠀⠀⠀⢠⢖⡒⢦⡀⠀⠀⠀⠀⡤⠂⠐⢄⠀⠀⠀⠀⢠⠖⢻⡤⡙⢤⣋⠀⠀⡤⠒⠒⢄⣀⣀⣴⠷⣉⡀⢹⡶⠋⢀⣤⠶⠋⠁⠀⠀⣧⠤⣸⣧⣊⢠⣣⠞⡢⡄⠀⠀⠀⠀⡠⠒⠒⢼⠐⡀⢂⢂⡁⠒⢠⢸⠀⠀⠀⠀⠀⡠⢀⠀⠄\n";
    cout << "⡐⠀⠀⠀⠀⢼⠢⡜⢢⡗⠀⠀⠀⠀⠇⠀⠀⣸⠀⠀⠀⠀⢸⡀⠀⢓⡅⠀⠙⠃⠀⣧⠜⢚⠏⣴⣰⢯⠞⣍⡃⣾⠀⢰⠋⠀⠀⢧⠀⠀⡼⠸⢀⢡⠀⣈⡟⠧⣜⣡⡟⠀⠀⠀⠀⢇⠀⠀⣈⡇⡐⠂⡄⠤⠑⢂⢸⠀⠀⠀⠀⠀⢇⠂⠌⠰\n";
    cout << "⠀⠀⠀⠀⠀⠀⠉⠚⠉⠀⠀⠀⠀⠀⠈⠁⠈⠀⠀⠀⠀⠀⠀⠉⠚⠉⠀⠀⠀⢀⠔⠁⢀⡞⣨⣧⣼⣷⣶⣶⣿⣧⣤⣷⣶⣶⣦⣤⣧⡞⠁⡇⠤⡟⠠⢸⠁⠀⠈⠣⡄⠀⠀⠀⠀⠈⠑⠊⠁⠸⡠⢁⡐⠄⣁⠢⢸⠀⠀⠀⠀⠀⠈⠁⠈⠀\n";
    cout << "⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠋⠀⢀⣾⣝⡻⡽⣿⢿⣻⡿⣿⣻⣿⣿⡿⣿⠿⣿⠿⡿⢷⡇⢂⠗⡀⢺⠀⠀⠀⣸⠈⢆⠀⠀⠀⠀⠀⠀⠀⠀⢧⢂⠐⠤⢀⠂⠹⠀⠀⠀⠀⠀⠀⠀⠀⠀\n";
    cout << "⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣐⢣⠀⠀⢸⡷⣎⡷⣹⣿⣟⣯⣿⣿⣏⣿⣿⣽⢿⣟⡼⣫⣝⡟⠇⢨⡇⠐⡟⠀⠀⠀⣷⠀⠸⡄⠀⠀⠀⠀⠀⠀⠀⢸⡄⢊⠐⡠⢉⠐⡇⠀⠀⠀⠀⠀⠀⠀⠀\n";
    cout << "⡑⢢⢄⠀⠀⠀⠀⣰⢫⡙⡝⣆⠀⠀⠀⢀⠖⠁⠈⢣⡀⠀⠀⠀⣰⠊⢩⠃⣷⠀⠀⣼⠀⣎⣿⣿⢷⣻⣿⡿⣽⠇⣿⣿⣯⣿⣻⣾⢷⡾⢰⠈⢰⡇⠂⡇⠀⠀⠀⡟⠀⠀⢓⠀⠀⠀⠀⠴⠉⠈⢑⢿⡄⢂⡐⠄⠊⡇⠙⣦⠀⠀⠀⠀⠀⠄\n";
    cout << "⡑⠊⠜⠀⡤⡄⠀⠙⣆⣜⣰⠏⡀⣀⢠⣤⢃⡀⣀⡼⠁⢀⡀⣀⠐⢀⡏⢀⡗⣠⣄⡟⣰⣧⣸⢿⣿⣿⣿⣽⣿⠃⣿⣷⣿⣝⣻⣽⡟⠀⢸⠂⣹⠁⣸⠇⠀⠀⢠⠇⠀⠀⠘⡅⠀⠀⠀⠲⣀⣂⡼⠚⣷⡀⠆⢨⠁⢧⣠⠟⠀⠀⠀⠀⠀⠂\n";

// ⠀⡐⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⠏⡡⡐⡄⢂⠆⡘⠴⣩⣎⣷⣽⣿⣻⣿⢿⣿⣿⣿⣿⣿⡽⣎⡷⣭⣛⡼⢭⡳⣝⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡿⢭⢯⡽⣭⢯⣝
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⣿⡛⠀⠁⠀⠉⠁⢚⣮⣿⣿⢿⣽⣫⢿⣽⢞⠯⣳⢯⣷⣻⣯⣿⡿⣿⣼⣷⣞⣧⡻⣌⡗⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠓⠉⠈⠑⠈⠂⠉
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⣿⠓⠀⠀⠀⠀⣠⣴⣿⢯⢷⣫⢟⣼⠳⣏⢆⣋⣶⣿⣻⣾⣿⣟⣷⣿⣿⡿⣽⣿⣿⣿⣟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⣀⢀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢄⣹⣿⡿⢆⡄⠂⢄⣠⣿⣿⠿⣽⣾⠷⠟⠛⠋⠀⠈⠉⠀⠉⠁⠁⠉⠉⠙⠞⠻⠿⠿⣿⣯⣿⣻⣿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣡⢶⡶⣋⣛⣟⡻⢯
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⡿⣹⣶⣿⣽⣼⣿⣿⡿⢛⣋⣥⠶⣎⣀⣠⣀⣀⡀⣀⢀⡀⠀⠀⠀⠀⡀⢀⡲⢗⣿⣽⣻⢿⣿⣿⣿⡤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⣮⣷⣯⣷⣾⣿⣿
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⣿⡟⣼⣳⣽⢯⣿⣾⡿⢫⣜⣫⣥⣶⡿⠟⠉⢉⣉⣉⠛⠛⠿⠯⠽⠶⠾⠿⠛⠿⠿⣷⣾⣿⣿⢿⣾⣻⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⣟⡾⣳⢯⡿⣽⣻
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⣿⣿⢱⣿⣿⣞⣿⣿⣿⢫⣓⣮⣽⣭⣷⣶⣾⣷⣦⣌⣙⡻⢷⣦⣶⣶⠿⠟⣉⣴⣶⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⢯⢗⡯⢟⡽⢏⡿
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⣿⣟⣾⣿⠋⣼⣿⣿⣯⢗⣯⣍⣭⢏⣉⣩⣤⣶⣿⣿⣿⣿⣆⣀⣀⣴⣾⣿⣿⣿⣾⣶⣭⣉⣭⣟⣻⡿⣷⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠀⠘⠀⠈⠀⠈
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⡿⠿⠇⠀⠀⢠⣿⣿⣿⣯⢿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⢿⡿⣿⣿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⠐⠀⠀⠀⢀⠀⠀⣿⣿⣿⣿⢟⣾⠿⢻⢛⢿⣿⣿⣿⣿⣿⣿⠃⡔⠡⢎⠴⣉⠒⡀⢾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡷⠄⡀⠀⠀⠀⠠⠀⠢⢄⠢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣁⣤⣾⣿⣿⣿⣽⡟⠁⣠⣲⣿⣾⣿⣿⣿⣽⣿⣿⣿⣼⣷⣾⣻⣗⣮⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣭⢿⣿⣿⣿⣮⣄⡀⠄⠀⠀⠀⠀⠀⡁⠂⢑⠠⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⢄⠀⠤⠄⠀⠀⠀⠀⠀⠀⠀⢀⣤⣿⣿⣿⣿⣿⣟⡹⢣⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣷⣄⠠⠄⠀⠀⠀⠁⠀⠈⠀⠀⠤⢄⢀⠀⣀⠀
// ⠀⠀⢀⡀⠀⠀⠀⠁⠀⠀⠈⠀⡀⣀⣀⡄⠀⠀⣠⣖⣯⣿⣿⣿⣿⣿⣿⣧⣏⣿⣿⣿⡿⠿⡟⢻⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠟⣛⣿⡻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣮⣥⡀⠀⠀⠀⠠⢤⡀⠀⠀⠀⠈⢦⠀
// ⠀⠀⠀⠁⢀⣠⣤⣦⣴⡶⢫⠭⡱⣑⢎⣹⡲⢿⡱⣏⣾⣿⣿⣿⣿⣿⣿⡗⣮⣿⣿⡟⢀⣾⣿⣿⣧⠙⢿⣿⣿⣿⢣⡻⠟⠋⠻⣿⣿⣿⣿⣿⠟⠀⢰⣿⣿⣷⡌⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⢽⣢⢴⣋⣿⡶⣀⢆⡠⡐⢦⢆⡡
// ⣄⠶⣾⣿⣿⣿⣷⣯⣿⣾⣷⣿⣻⡽⣞⣷⣻⢏⣷⣛⡾⣿⣿⣿⣿⣿⣿⡟⡴⢟⣻⣥⣀⠛⢿⠿⢃⣺⣾⣿⣿⡗⠋⠁⡀⠀⠀⠘⣿⣯⣟⣿⣷⣶⣬⣻⣿⢯⣼⣿⣿⣿⣿⣿⣿⠿⠿⠛⠛⠛⢻⣯⡷⣽⢾⡽⣾⡽⣟⣾⡷⣽⣊⠾⡴
// ⣿⣿⣯⣿⣿⣿⣿⣿⣿⣿⣿⣯⣷⣿⢿⣽⣳⠿⣜⣳⣿⠉⠛⠻⢿⣷⣿⡧⣙⠆⠼⣿⣻⣿⣿⣿⣿⣿⣿⢿⠁⢀⠀⠀⡆⠀⡆⢀⡾⣽⡿⣾⣽⣾⣿⣿⣿⣿⢿⣯⢿⣻⣿⣿⣿⠀⠀⠀⠀⠀⣀⣽⢯⣽⣟⣿⣷⣻⣝⡾⣽⣻⡽⣯⣷
// ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣾⣿⣿⣯⣿⡽⣞⠷⣏⢢⢄⣸⣿⣿⡷⣩⢄⡀⠻⡹⣭⢻⣝⣻⣿⡅⢢⡈⣄⡦⠎⠁⠀⠒⠈⠳⢧⣛⡿⡾⣽⣯⢿⣽⡾⣿⣽⣻⢯⣿⣿⡇⠀⠀⡰⣉⠾⣽⣻⠾⣽⣾⣿⣾⣿⣯⣿⢷⣯⣟⣷⣿
// ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⠿⠿⢿⣷⣿⣹⣟⢯⣻⣬⣿⡿⣟⡳⣍⠶⣣⠀⠑⢎⣳⣮⠿⠁⢀⠒⣉⣠⢀⣀⣀⣀⣀⣤⣄⣤⣈⣝⡁⠣⠻⢿⡾⣹⢷⣹⢯⣟⣿⣿⣧⣧⣽⡵⣏⡾⣝⣳⣟⡿⠿⠿⢿⡻⢿⣽⣿⣞⣯⣿⣻
// ⣿⣿⣿⡿⠿⠿⠛⠛⠉⠉⠉⠀⠀⠀⠀⠀⠀⠈⠙⠷⣿⣯⣟⣿⣿⣯⠛⣿⣬⣛⢿⡲⣅⢊⠈⠀⠀⢀⣶⣿⣿⣿⣿⣶⣷⣾⣿⣾⣿⣿⣿⣿⣿⡄⠡⢂⡝⢧⣏⡿⣯⣟⣿⣿⣿⣿⣷⣿⣽⣾⣽⠾⣿⠀⠀⠀⢤⣴⣾⣿⢿⣯⣟⣷⣿
// ⠛⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⣇⡀⠉⠉⠙⢻⣿⢡⣿⣧⣻⣮⣷⡽⢦⠁⡂⠀⠘⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⣀⠣⡜⣼⣳⣾⢿⣳⣿⣿⡿⠛⠉⠈⠙⠛⠉⠀⠀⠀⠀⠀⠀⠈⣿⣯⡽⣞⣷⣯⣿⠞
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠣⡐⠀⠣⡀⠀⢻⠧⠼⢿⣯⣷⢯⣟⣷⡘⣄⠀⠀⣾⣿⣏⠳⡭⢟⣿⡻⣟⣿⣿⣿⣿⣿⣷⣄⢚⡽⣷⣻⣽⣻⣽⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣷⣿⡿⠟⠋⣡⢚
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡁⠹⣠⠀⠣⠀⠀⠀⠀⣼⣿⡽⣯⢿⣞⡷⡌⠆⠄⠙⠃⠌⡐⠠⠀⠈⠙⠉⠁⠐⢬⣿⣿⣿⣧⣾⡿⣽⣳⢯⣻⣟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡸⢿⡛⠁⠠⠀⠐⡤⢻
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠈⠛⡜⠄⠸⡀⠀⠰⣿⣿⣳⢽⣚⡮⣗⢯⡜⡌⢆⠍⡈⠄⡀⣀⣀⣀⣠⡒⣤⠘⡙⢾⣯⣿⢿⣽⡿⣽⣚⣿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠀⡀⣤⠿⣘⣲⡷⠀⢀⡆⣼⠡⢿
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠇⠀⠀⠌⢆⢠⡘⢆⠀⠙⢿⣟⡎⢷⣙⢮⡳⡼⡹⣼⣾⢿⣻⣿⣿⣿⣿⣿⣿⣿⣿⡿⣷⣟⣿⣿⣾⡟⣴⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣖⣧⣼⣯⢳⡙⢦⡿⢀⣠⢨⠀⣿⣈⢿
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢤⣧⠀⠑⠄⠀⢻⡼⢣⡝⣲⡹⡵⣯⣿⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣾⢻⣿⢓⢾⡿⠁⠀⠀⠀⠀⠀⠀⢀⠄⠀⣠⡿⣿⣿⣍⣿⣧⣿⡿⠀⠀⠐⠛⠈⠓⠈⠛
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀⠀⠀⢙⢶⠤⠀⠠⢸⣿⣷⡜⣡⠳⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣽⢊⣾⡇⠀⠀⠀⠀⠀⠀⠀⠸⠀⣰⣿⡟⠻⠃⠉⠀⠀⠀⠀⠁⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠒⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠑⣌⡀⡀⣿⣿⣿⡤⢓⣼⣟⣻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣽⢹⣾⣿⠄⠀⠀⠀⠀⠀⠀⢾⣧⠘⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢆⡀⢀⠢⠤⠖⠁⠚⠃⠀⠹⣿⣿⣧⢣⡘⡿⣘⢎⡯⣟⣿⢿⡿⣿⣿⢿⡟⣿⢫⠷⣿⣧⣿⣿⡇⠀⠀⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠀⠀⠀⠀⠀⠀⠊⠉⠀⠀⠀⠀⠀⠀⠀⠸⣞⣿⣿⣿⡄⢷⣩⢎⢷⡹⣎⠿⣜⢳⣎⢷⡹⣖⢯⣻⢧⣷⣿⣿⡇⠀⠀⠀⠀⢀⡆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣯⠀⠀⢹⣿⣿⣿⣿⣯⢷⣪⢷⣫⡽⣻⡼⣳⢮⡗⣯⡽⣾⣽⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠱⣡⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⣿⣿⣿⣿⣿⣿⣷⣯⣷⣯⣷⣯⣿⣾⣷⣿⣿⣿⣿⣿⣿⠃⠀⠀⠀⠀⠀⠀⠀⢹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⡅⠀⠀⠀⠀⠀⠀⠄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣄⠀⠀⠘⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠟⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⣿⠀⠀⠀⠀⠀⠐⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⢳⠄⠀⠀⠀⠀⠈⠉⠉⠉⠉⠻⢟⣛⡻⠋⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⣿⠀⠀⠀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠛⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⣿⡆⠂⠀⠠⢁⠀⠈⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠇⠀⠀⠀
// ⣿⣷⡀⠀⠀⠈⠀⠀⠀⠄⠀⠀⠠⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⡌⠀⡀⠀
// ⠿⣻⣧⠀⠀⠠⠀⠀⠀⢈⢂⠀⠀⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠷⠀⡶⡕⢀
// ⠀⠈⢿⣧⡀⠰⠁⠀⠂⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣏⠀⡜⡇⢀⣋
// ⠀⠀⠸⠻⢀⣤⣅⡂⠁⠀⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡿⠆⡸⢁⣴⣿⡏
// ⢠⣴⠧⣴⣿⣿⣿⣿⣿⣤⡙⡃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⢺⠟⠂⣴⢻⣿⢿⡃
// ⣿⢩⣿⣩⣫⣽⣯⣽⣿⣿⡎⠳⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⢀⣧⠞⣑⢺⣯⡿⡄
// ⡈⢁⣾⣿⣿⣿⣿⣽⣭⣬⣿⣬⠁⠀⠀⠐⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⠀⠀⠀⢡⡾⢛⡌⣮⢽⡷⡟⡅
// ⣶⣦⣿⣽⣟⢻⣿⣿⣿⣟⣛⣟⣷⡄⠀⠢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡄⠊⠠⣤⣿⡱⣧⣼⣦⣿⣽⣯⠁
// ⠉⠛⠛⠛⠿⠿⠾⢯⣭⣭⣭⣯⣛⣏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡐⠀⠀⠀⣿⣯⡵⣭⢦⣽⣏⣾⢟⡀

// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣄⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⢀⣴⠂⢀⣀⣴⡆⠀⠀⠀⠀⠀⠀⠀⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡄⠀⠀⠀⠀
// ⠀⠀⠀⠀⢸⣯⡠⠜⠛⠛⠃⠀⠀⠀⠀⠀⠀⡼⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀⠀
// ⠀⠄⠒⠊⢹⡇⢠⡖⠀⠀⠀⠀⠀⠀⠀⢀⠞⣠⢏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀
// ⠀⠀⠀⢀⣿⣷⡿⢷⣆⠀⠀⠀⠀⠀⢀⣾⣿⡟⢈⣿⡿⣱⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⠀
// ⠀⢀⡶⠋⢿⣿⠃⢈⡿⠀⠀⠀⠀⠀⣾⣿⣟⣰⣿⡿⢁⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠀
// ⠀⢿⣄⢀⣼⣇⠀⠼⠇⠀⠀⠀⠀⣼⣿⣿⣿⣿⣿⢃⣾⣿⣿⣿⣟⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀
// ⠀⠀⠉⠁⢈⡙⠀⠀⠀⠀⢀⠀⢠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀
// ⠀⠀⠀⠀⣿⡤⠴⠒⢹⣿⣿⠀⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢃⠏⢈⣿⣿⣿⣿⣿⣿⣿⡿⢻⣿⣿⣿⣿⡇
// ⣀⡤⠒⠙⣿⠀⣠⠆⠈⠉⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⠥⢯⣀⣜⣿⣿⣿⣿⣿⠿⡿⠃⢸⣿⣿⣿⣿⡇
// ⠀⠀⠀⢀⣿⣼⠧⣤⡀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢁⣴⣶⣶⠀⠹⡆⠙⠋⠉⠀⢾⣕⠒⢻⣿⣿⣿⣿⡇
// ⠀⣠⠞⢹⣿⠁⠀⠈⣿⡄⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣸⡟⣛⡟⠀⠀⠋⠀⠀⠀⢠⣿⣿⠀⣼⣿⣿⣿⣿⠃
// ⢰⣏⣰⠟⠿⠄⠀⠀⠿⠃⠀⠀⠸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠉⠉⠁⠀⠀⠀⠀⠀⠀⠀⠈⠛⣡⢴⣿⣿⣿⣿⣿⠀
// ⠀⠉⠀⠀⠀⠀⢀⡄⠀⣀⣶⣶⣆⠈⠈⠻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣿⣿⣿⣿⡿⠀
// ⠀⠀⠀⠀⢀⣠⣼⠗⠉⠀⡈⠉⠁⠀⠀⠀⠀⢈⡿⢿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣿⠇⠀
// ⡀⣀⠀⠚⠉⠀⣿⡤⣤⣿⡁⠀⠀⠀⠀⢠⠒⣱⡇⠀⠈⢻⣿⣿⣿⣿⣿⣿⣇⠀⠀⠀⠀⠀⠀⡀⠀⠀⠀⣠⣴⣿⣿⣿⡿⠻⠋⠀⠀
// ⡇⣿⠀⠀⢀⡴⣿⣶⠏⠈⢿⡄⠀⡰⠒⠙⡞⣿⡇⠀⠀⠈⢇⠈⠉⠉⠉⢿⠿⢟⣲⣄⣀⠀⢀⡠⢴⣶⣿⣏⠙⠻⣏⠁⠀⠀⠠⠀⠀
// ⠀⠀⠀⢀⣾⣡⠿⡧⠀⠀⢈⡤⠊⠀⠀⢀⢣⢹⡇⠀⠀⠀⠈⡄⠀⠀⠀⠈⢿⡰⠛⠻⢆⠉⠁⠀⢀⡬⡻⣿⡆⠀⠈⢆⠀⠀⠈⠀⠀
// ⡀⠀⠀⠀⠉⠀⠀⠀⡠⠖⠁⠀⠀⠀⡠⠚⢸⣾⡇⠀⠀⠀⠀⠘⡄⠀⠀⠀⠀⠧⠀⠀⠀⠱⣄⠀⡌⠀⢹⣿⣿⠀⠀⠸⡀⠀⠀⠀⠀
// ⡧⠀⠀⠀⠀⠀⢀⡞⠀⠒⠒⢄⠀⠊⠀⠀⠆⣿⣇⠀⣠⠒⠢⢄⠹⡄⠀⠀⠀⠀⠀⠀⢀⡜⠈⢆⠑⢤⠀⢿⣿⡇⡄⠀⡇⠀⠀⠀⠀
// ⠇⠀⠀⠀⠀⠀⡜⠀⠀⠀⠀⠀⠱⡄⠀⠀⠀⣿⣿⣼⣿⠀⠀⠈⢷⠱⣀⡀⠀⠀⠀⠀⠎⠀⠀⠈⣆⠘⠀⢸⣿⣧⠁⢀⡇⠀⠀⠀⠀
// ⡄⠀⠀⠀⠀⢀⠃⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⣿⣿⣿⣿⠀⠀⢀⡇⠀⠱⡀⠀⠀⠀⠀⠀⠀⠀⠀⢘⣆⠀⢸⣿⡇⠀⢈⠀⠀⠀⠀⠀
// ⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⠀⠀⠈⠓⠦⡀⠱⡀⠀⠀⠀⠀⠀⢀⣤⣾⣿⡄⠀⢿⡇⠀⢀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⡇⠀⠀⠀⠀⠀⠈⢢⡱⣄⣀⣤⣴⣾⣿⣿⣿⣿⣷⠀⠈⢧⠀⡆⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⠃⠀⠀⠀⠀⠀⠀⠀⠑⣌⢻⣿⣿⣿⣿⣿⣿⣿⣿⡆⠀⠈⣶⠇⠀⠀⠀⠀⠀

}