---

#include <iostream>
#include <cstring>

struct Student {
    char fam[50];
    int group;
    int mark;
};

const int N = 6;
const int M = 15;

int hash(int key, int m) {
    return key % m;
}

void addToHashTable(Student* table, int* status, Student s, int m) {
    int i = hash(s.mark, m);
    int p = 1;
    while (status[i] == 1) {
        i = (i + p * p) % m;
        p++;
    }
    table[i] = s;
    status[i] = 1;
}

int searchInHashTable(Student* table, int* status, int key, int m) {
    int i = hash(key, m);
    int p = 1;
    int start = i;
    while (status[i] != 0) {
        if (status[i] == 1 && table[i].mark == key) return i;
        i = (i + p * p) % m;
        p++;
        if (i == start) break;
    }
    return -1;
}

int main() {
    Student students[N];
    std::cout << "Vvedite dannye o " << N << " studentah (familija, gruppa, ocenka):" << std::endl;
    for (int i = 0; i < N; i++) {
        std::cin >> students[i].fam >> students[i].group >> students[i].mark;
    }

    Student hashTable[M];
    int status[M];
    for (int i = 0; i < M; i++) {
        status[i] = 0;
    }

    for (int i = 0; i < N; i++) {
        addToHashTable(hashTable, status, students[i], M);
    }

    std::cout << "\nIshodnyj massiv:" << std::endl;
    for (int i = 0; i < N; i++) {
        std::cout << students[i].fam << " " << students[i].group << " " << students[i].mark << std::endl;
    }

    std::cout << "\nHesh-tablica (kvadratichnaya adresaciya, razmer " << M << "):" << std::endl;
    for (int i = 0; i < M; i++) {
        std::cout << "H[" << i << "] = ";
        if (status[i] == 0) std::cout << "svobodno" << std::endl;
        else std::cout << hashTable[i].fam << " " << hashTable[i].group << " " << hashTable[i].mark << std::endl;
    }

    std::cout << "\nPoisk po klyuchu (ocenka). Dlya vyhoda vvedite -1:" << std::endl;
    int key;
    while (true) {
        std::cout << "Vvedite ocenku: ";
        if (!(std::cin >> key)) {
            std::cin.clear();
            std::cin.ignore(10000, '\n');
            std::cout << "Oshibka vvoda" << std::endl;
            continue;
        }
        if (key == -1) break;
        int idx = searchInHashTable(hashTable, status, key, M);
        if (idx == -1) std::cout << "Net elementa" << std::endl;
        else {
            std::cout << "Najdeno: " << hashTable[idx].fam << " "
                      << hashTable[idx].group << " " << hashTable[idx].mark << std::endl;
        }
    }
    return 0;
}