// tsp_tour

#include<bits/stdc++.h>
using namespace std;

void primMST(vector<vector<pair<int,int>>> &adj, vector<vector<int>> &mst)
{
    int V = adj.size();

    vector<int> parent(V,-1);
    vector<int> key(V,INT_MAX);
    vector<int> visited(V,0);

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

    key[0] = 0;
    pq.push({0,0});

    while(!pq.empty()){

        pair<int,int> p = pq.top();
        pq.pop();

        int wt = p.first;
        int u = p.second;

        if(visited[u])
            continue;

        visited[u] = 1;

        for(auto v : adj[u]){
            if(!visited[v.first] && v.second < key[v.first]){
                key[v.first] = v.second;
                pq.push({key[v.first],v.first});
                parent[v.first] = u;
            }
        }
    }

    for(int i = 1; i < V; i++){
        mst[parent[i]].push_back(i);
    }


    return;

}

void dfs(vector<vector<int>> &mst, vector<int> &visited, vector<int> &tsp, int u){

    visited[u] = true;
    tsp.push_back(u);

    for(auto v : mst[u]){
        if(!visited[v]){
            dfs(mst,visited,tsp,v);
        }
    }
}

int main(){

    #ifndef ONLINE_JUDGE
        freopen("../input.txt", "r", stdin);
        freopen("../output.txt", "w", stdout);
    #endif

    int n,e;
    cin >> n >> e;

    vector<vector<pair<int,int>>> adj(n);

    for(int i = 0; i < e; i++){
        int u,v,w;
        cin >> u >> v >> w;

        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    vector<vector<int>> mst(n);

    primMST(adj,mst);

    vector<int> visited(n,0);

    vector<int> tsp;
    dfs(mst,visited,tsp,0);

    tsp.push_back(0);

    for(auto i : tsp){
        cout << i << " ";
    }

}

// vertex cover

#include<bits/stdc++.h>
using namespace std;

void printVertexCover(vector<vector<int>> &adj){

    int V = adj.size();
    vector<bool> visited(V,false);

    for(int u = 0; u < V; u++){
        if(!visited[u]){
            for(auto v : adj[u]){
                if(!visited[v]){
                    visited[u] = true;
                    visited[v] = true;
                    break;
                }
            }
        }
    }

    for(int i = 0; i < V; i++){
        if(visited[i]){
            cout << i << " ";
        }
    }
}

int main(){

    #ifndef ONLINE_JUDGE
        freopen("../input.txt", "r", stdin);
        freopen("../output.txt", "w", stdout);
    #endif

    int n,e;
    cin >> n >> e;

    vector<vector<int>> adj(n);

    for(int i = 0; i < e; i++){
        int u,v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    printVertexCover(adj);
    adj.clear();

}

// Navie
#include <bits/stdc++.h>
using namespace std;

void NaiveSearchPattern(string txt, string pat)
{
    int n = txt.size();
    int m = pat.size();

    for(int i = 0; i <= n-m; i++){

        int j;

        for(j = 0; j < m; j++)
            if(txt[i + j] != pat[j])
                break;

        if(j == m)
            cout << "Pattern found at index " << i << endl;
    }
}

int main()
{

    #ifndef ONLINE_JUDGE
        freopen("../input.txt", "r", stdin);
        freopen("../output.txt", "w", stdout);
    #endif

    string str,pat;
    cin >> str >> pat;

    NaiveSearchPattern(str,pat);
}

// Automata

#include <bits/stdc++.h>
using namespace std;

int NUM_OF_CHARS = 256;

vector<vector<int>> computeTF(string ptr) {
    int m = ptr.size();
    vector<vector<int>> TFtable(m + 1, vector<int>(NUM_OF_CHARS));

    for (int i = 0; i < NUM_OF_CHARS; i++) TFtable[0][i] = 0;
    TFtable[0][ptr[0]] = 1;

    int lps = 0;
    for (int i = 1; i <= m; i++) {
        for (int x = 0; x < NUM_OF_CHARS; x++) TFtable[i][x] = TFtable[lps][x];

        TFtable[i][ptr[i]] = i + 1;
        if (lps < m) lps = TFtable[lps][ptr[i]];
    }
    return TFtable;
}

void finiteAutomataStringMatcher(string txt, string ptr) {
    int n = txt.size();
    int m = ptr.size();
    vector<vector<int>> TF = computeTF(ptr);
    int j = 0;
    for (int i = 0; i < n; i++) {
        j = TF[j][txt[i]];
        if (j == m) {
            cout << "Pattern found with shift " << i - m + 1 << "\n";
        }
    }
}

int main() {
    string txt, ptr;
    cin >> txt >> ptr;

    finiteAutomataStringMatcher(txt, ptr);

    return 0;
}


// kmp

#include <bits/stdc++.h>
using namespace std;

void computeLPSArray(char *pat, int M, int *lps);

void KMPSearch(char *pat, char *txt)
{
    int M = strlen(pat);
    int N = strlen(txt);

    int lps[M];

    computeLPSArray(pat, M, lps);

    int i = 0;
    int j = 0;
    while ((N - i) >= (M - j))
    {
        if (pat[j] == txt[i])
        {
            j++;
            i++;
        }

        if (j == M)
        {
            printf("Found pattern at index %d ", i - j);
            j = lps[j - 1];
        }

        else if (i < N && pat[j] != txt[i])
        {
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
}

void computeLPSArray(char *pat, int M, int *lps)
{

    int len = 0;

    lps[0] = 0;

    int i = 1;
    while (i < M)
    {
        if (pat[i] == pat[len])
        {
            len++;
            lps[i] = len;
            i++;
        }
        else
        {
            if (len != 0)
            {
                len = lps[len - 1];
            }
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int main()
{
    char txt[] = "ABABDABACDABABCABAB";
    char pat[] = "ABABCABAB";
    KMPSearch(pat, txt);
    return 0;
}

/// avl_deletion
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
    int height;
    Node(int x) {
        key = x;
        left = NULL;
        right = NULL;
        height = 1;
    }
};

int height(Node *x) {
    if (!x) return 0;
    return x->height;
}

int getBalanceFactor(Node *N) {
    if (!N) return 0;
    return height(N->left) - height(N->right);
}

// left rotate function

Node *leftRotate(Node *x) {
    Node *y = x->right;
    Node *T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = 1 + max(height(x->left), height(x->right));
    y->height = 1 + max(height(y->left), height(y->right));
    return y;
}

Node *rightRotate(Node *y) {
    Node *x = y->left;
    Node *T2 = x->right;

    x->right = y;
    y->left = T2;

    x->height = 1 + max(height(x->left), height(x->right));
    y->height = 1 + max(height(y->left), height(y->right));

    return x;
}

Node *insert(Node *node, int key) {
    if (!node) return new Node(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;

    node->height = 1 + max(height(node->left), height(node->right));
    int balanceFactor = getBalanceFactor(node);

    if (balanceFactor > 1 && key < node->left->key) {
        return rightRotate(node);
    }

    if (balanceFactor < -1 && key > node->right->key) {
        return leftRotate(node);
    }

    if (balanceFactor > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    if (balanceFactor < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}

void preOrder(Node *node) {
    if (!node) return;
    cout << node->key << " ";
    preOrder(node->left);
    preOrder(node->right);
}

Node *minValueNode(Node *root) {
    Node *curr = root;
    while (curr->left) {
        curr = curr->left;
    }
    return curr;
}

Node *deleteNode(Node *node, int key) {
    if (!node) return node;
    if (key < node->key)
        deleteNode(node->left, key);
    else if (key > node->key)
        deleteNode(node->right, key);
    else {
        if (node->left == NULL || node->right == NULL) {
            Node *temp = node->left ? node->left : node->right;
            if (temp == NULL) {
                temp = node;
                node = NULL;
            } else {
                *node = *temp;
            }
            free(temp);
        } else {
            Node *temp = minValueNode(node->right);
            node->key = temp->key;
            node->right = deleteNode(node->right, temp->key);
        }
    }

    if (!node) return node;

    node->height = 1 + max(height(node->right), height(node->left));

    int balanceFactor = getBalanceFactor(node);

    if (balanceFactor > 1 && getBalanceFactor(node->left) >= 0) {
        return rightRotate(node);
    }

    if (balanceFactor > 1 && getBalanceFactor(node->left) < 0) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    if (balanceFactor < -1 && getBalanceFactor(node->right) < 0) {
        return leftRotate(node);
    }
    if (balanceFactor < -1 && getBalanceFactor(node->right) >= 0) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}

int main() {
    Node *root = NULL;
    root = insert(root, 9);
    root = insert(root, 5);
    root = insert(root, 10);
    root = insert(root, 0);
    root = insert(root, 6);
    root = insert(root, 11);
    root = insert(root, -1);
    root = insert(root, 1);
    root = insert(root, 2);

    cout << "Preorder traversal of the "
            "constructed AVL tree is \n";
    preOrder(root);
    cout << "\n";
    deleteNode(root, 10);

    preOrder(root);
    return 0;
}

//avl insertion
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
    int height;
    Node(int x) {
        key = x;
        left = NULL;
        right = NULL;
        height = 1;
    }
};

int height(Node *x) {
    if (!x) return 0;
    return x->height;
}

int getBalanceFactor(Node *N) {
    if (!N) return 0;
    return height(N->left) - height(N->right);
}

// left rotate function

Node *leftRotate(Node *x) {
    Node *y = x->right;
    Node *T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = 1 + max(height(x->left), height(x->right));
    y->height = 1 + max(height(y->left), height(y->right));
    return y;
}

Node *rightRotate(Node *y) {
    Node *x = y->left;
    Node *T2 = x->right;

    x->right = y;
    y->left = T2;

    x->height = 1 + max(height(x->left), height(x->right));
    y->height = 1 + max(height(y->left), height(y->right));

    return x;
}

Node *insert(Node *node, int key) {
    if (!node) return new Node(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;

    node->height = 1 + max(height(node->left), height(node->right));
    int balanceFactor = getBalanceFactor(node);

    if (balanceFactor > 1 && key < node->left->key) {
        return rightRotate(node);
    }

    if (balanceFactor < -1 && key > node->right->key) {
        return leftRotate(node);
    }

    if (balanceFactor > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    if (balanceFactor < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}

void preOrder(Node *node) {
    if (!node) return;
    cout << node->key << " ";
    preOrder(node->left);
    preOrder(node->right);
}

int main() {
    Node *root = NULL;
    root = insert(root, 10);

    root = insert(root, 20);

    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    cout << "Preorder traversal of the "
            "constructed AVL tree is \n";
    preOrder(root);
    return 0;
}


// binomial heap


#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int data, degree;
    Node *child, *sibling, *parent;
};

Node *newNode(int key)
{
    Node *temp = new Node;
    temp->data = key;
    temp->degree = 0;
    temp->child = temp->parent = temp->sibling = NULL;
    return temp;
}

Node *mergeBinomialTrees(Node *b1, Node *b2)
{

    if (b1->data > b2->data)
        swap(b1, b2);

    b2->parent = b1;
    b2->sibling = b1->child;
    b1->child = b2;
    b1->degree++;

    return b1;
}

list<Node *> unionBionomialHeap(list<Node *> l1,
                                list<Node *> l2)
{

    list<Node *> _new;
    list<Node *>::iterator it = l1.begin();
    list<Node *>::iterator ot = l2.begin();
    while (it != l1.end() && ot != l2.end())
    {

        if ((*it)->degree <= (*ot)->degree)
        {
            _new.push_back(*it);
            it++;
        }

        else
        {
            _new.push_back(*ot);
            ot++;
        }
    }

    while (it != l1.end())
    {
        _new.push_back(*it);
        it++;
    }

    while (ot != l2.end())
    {
        _new.push_back(*ot);
        ot++;
    }
    return _new;
}

list<Node *> adjust(list<Node *> _heap)
{
    if (_heap.size() <= 1)
        return _heap;
    list<Node *> new_heap;
    list<Node *>::iterator it1, it2, it3;
    it1 = it2 = it3 = _heap.begin();

    if (_heap.size() == 2)
    {
        it2 = it1;
        it2++;
        it3 = _heap.end();
    }
    else
    {
        it2++;
        it3 = it2;
        it3++;
    }
    while (it1 != _heap.end())
    {

        if (it2 == _heap.end())
            it1++;

        else if ((*it1)->degree < (*it2)->degree)
        {
            it1++;
            it2++;
            if (it3 != _heap.end())
                it3++;
        }

        else if (it3 != _heap.end() &&
                 (*it1)->degree == (*it2)->degree &&
                 (*it1)->degree == (*it3)->degree)
        {
            it1++;
            it2++;
            it3++;
        }

        else if ((*it1)->degree == (*it2)->degree)
        {
            Node *temp;
            *it1 = mergeBinomialTrees(*it1, *it2);
            it2 = _heap.erase(it2);
            if (it3 != _heap.end())
                it3++;
        }
    }
    return _heap;
}

list<Node *> insertATreeInHeap(list<Node *> _heap,
                               Node *tree)
{

    list<Node *> temp;

    temp.push_back(tree);

    temp = unionBionomialHeap(_heap, temp);

    return adjust(temp);
}

list<Node *> removeMinFromTreeReturnBHeap(Node *tree)
{
    list<Node *> heap;
    Node *temp = tree->child;
    Node *lo;

    while (temp)
    {
        lo = temp;
        temp = temp->sibling;
        lo->sibling = NULL;
        heap.push_front(lo);
    }
    return heap;
}

list<Node *> insert(list<Node *> _head, int key)
{
    Node *temp = newNode(key);
    return insertATreeInHeap(_head, temp);
}

Node *getMin(list<Node *> _heap)
{
    list<Node *>::iterator it = _heap.begin();
    Node *temp = *it;
    while (it != _heap.end())
    {
        if ((*it)->data < temp->data)
            temp = *it;
        it++;
    }
    return temp;
}

list<Node *> extractMin(list<Node *> _heap)
{
    list<Node *> new_heap, lo;
    Node *temp;

    temp = getMin(_heap);
    list<Node *>::iterator it;
    it = _heap.begin();
    while (it != _heap.end())
    {
        if (*it != temp)
        {

            new_heap.push_back(*it);
        }
        it++;
    }
    lo = removeMinFromTreeReturnBHeap(temp);
    new_heap = unionBionomialHeap(new_heap, lo);
    new_heap = adjust(new_heap);
    return new_heap;
}

void printTree(Node *h)
{
    while (h)
    {
        cout << h->data << " ";
        printTree(h->child);
        h = h->sibling;
    }
}

void printHeap(list<Node *> _heap)
{
    list<Node *>::iterator it;
    it = _heap.begin();
    while (it != _heap.end())
    {
        printTree(*it);
        it++;
    }
}

int main()
{
    int ch, key;
    list<Node *> _heap;

    _heap = insert(_heap, 10);
    _heap = insert(_heap, 20);
    _heap = insert(_heap, 30);

    cout << "Heap elements after insertion:\n";
    printHeap(_heap);

    Node *temp = getMin(_heap);
    cout << "\nMinimum element of heap "
         << temp->data << "\n";

    _heap = extractMin(_heap);
    cout << "Heap after deletion of minimum element\n";
    printHeap(_heap);

    return 0;
}


// fibonacci heap
#include <bits/stdc++.h>
using namespace std;

struct node
{
    node *parent;
    node *child;
    node *left;
    node *right;
    int key;
    int degree;
    char mark;
    char c;
};

struct node *mini = NULL;

int no_of_nodes = 0;

void insertion(int val)
{
    struct node *new_node = new node();
    new_node->key = val;
    new_node->degree = 0;
    new_node->mark = 'W';
    new_node->c = 'N';
    new_node->parent = NULL;
    new_node->child = NULL;
    new_node->left = new_node;
    new_node->right = new_node;
    if (mini != NULL)
    {
        (mini->left)->right = new_node;
        new_node->right = mini;
        new_node->left = mini->left;
        mini->left = new_node;
        if (new_node->key < mini->key)
            mini = new_node;
    }
    else
    {
        mini = new_node;
    }
    no_of_nodes++;
}

void Fibonnaci_link(struct node *ptr2, struct node *ptr1)
{
    (ptr2->left)->right = ptr2->right;
    (ptr2->right)->left = ptr2->left;
    if (ptr1->right == ptr1)
        mini = ptr1;
    ptr2->left = ptr2;
    ptr2->right = ptr2;
    ptr2->parent = ptr1;
    if (ptr1->child == NULL)
        ptr1->child = ptr2;
    ptr2->right = ptr1->child;
    ptr2->left = (ptr1->child)->left;
    ((ptr1->child)->left)->right = ptr2;
    (ptr1->child)->left = ptr2;
    if (ptr2->key < (ptr1->child)->key)
        ptr1->child = ptr2;
    ptr1->degree++;
}

void Consolidate()
{
    int temp1;
    float temp2 = (log(no_of_nodes)) / (log(2));
    int temp3 = temp2;
    struct node *arr[temp3 + 1];
    for (int i = 0; i <= temp3; i++)
        arr[i] = NULL;
    node *ptr1 = mini;
    node *ptr2;
    node *ptr3;
    node *ptr4 = ptr1;
    do
    {
        ptr4 = ptr4->right;
        temp1 = ptr1->degree;
        while (arr[temp1] != NULL)
        {
            ptr2 = arr[temp1];
            if (ptr1->key > ptr2->key)
            {
                ptr3 = ptr1;
                ptr1 = ptr2;
                ptr2 = ptr3;
            }
            if (ptr2 == mini)
                mini = ptr1;
            Fibonnaci_link(ptr2, ptr1);
            if (ptr1->right == ptr1)
                mini = ptr1;
            arr[temp1] = NULL;
            temp1++;
        }
        arr[temp1] = ptr1;
        ptr1 = ptr1->right;
    } while (ptr1 != mini);
    mini = NULL;
    for (int j = 0; j <= temp3; j++)
    {
        if (arr[j] != NULL)
        {
            arr[j]->left = arr[j];
            arr[j]->right = arr[j];
            if (mini != NULL)
            {
                (mini->left)->right = arr[j];
                arr[j]->right = mini;
                arr[j]->left = mini->left;
                mini->left = arr[j];
                if (arr[j]->key < mini->key)
                    mini = arr[j];
            }
            else
            {
                mini = arr[j];
            }
            if (mini == NULL)
                mini = arr[j];
            else if (arr[j]->key < mini->key)
                mini = arr[j];
        }
    }
}

void Extract_min()
{
    if (mini == NULL)
        cout << "The heap is empty" << endl;
    else
    {
        node *temp = mini;
        node *pntr;
        pntr = temp;
        node *x = NULL;
        if (temp->child != NULL)
        {

            x = temp->child;
            do
            {
                pntr = x->right;
                (mini->left)->right = x;
                x->right = mini;
                x->left = mini->left;
                mini->left = x;
                if (x->key < mini->key)
                    mini = x;
                x->parent = NULL;
                x = pntr;
            } while (pntr != temp->child);
        }
        (temp->left)->right = temp->right;
        (temp->right)->left = temp->left;
        mini = temp->right;
        if (temp == temp->right && temp->child == NULL)
            mini = NULL;
        else
        {
            mini = temp->right;
            Consolidate();
        }
        no_of_nodes--;
    }
}

void Cut(struct node *found, struct node *temp)
{
    if (found == found->right)
        temp->child = NULL;

    (found->left)->right = found->right;
    (found->right)->left = found->left;
    if (found == temp->child)
        temp->child = found->right;

    temp->degree = temp->degree - 1;
    found->right = found;
    found->left = found;
    (mini->left)->right = found;
    found->right = mini;
    found->left = mini->left;
    mini->left = found;
    found->parent = NULL;
    found->mark = 'B';
}

void Cascase_cut(struct node *temp)
{
    node *ptr5 = temp->parent;
    if (ptr5 != NULL)
    {
        if (temp->mark == 'W')
        {
            temp->mark = 'B';
        }
        else
        {
            Cut(temp, ptr5);
            Cascase_cut(ptr5);
        }
    }
}

void Decrease_key(struct node *found, int val)
{
    if (mini == NULL)
        cout << "The Heap is Empty" << endl;

    if (found == NULL)
        cout << "Node not found in the Heap" << endl;

    found->key = val;

    struct node *temp = found->parent;
    if (temp != NULL && found->key < temp->key)
    {
        Cut(found, temp);
        Cascase_cut(temp);
    }
    if (found->key < mini->key)
        mini = found;
}

void Find(struct node *mini, int old_val, int val)
{
    struct node *found = NULL;
    node *temp5 = mini;
    temp5->c = 'Y';
    node *found_ptr = NULL;
    if (temp5->key == old_val)
    {
        found_ptr = temp5;
        temp5->c = 'N';
        found = found_ptr;
        Decrease_key(found, val);
    }
    if (found_ptr == NULL)
    {
        if (temp5->child != NULL)
            Find(temp5->child, old_val, val);
        if ((temp5->right)->c != 'Y')
            Find(temp5->right, old_val, val);
    }
    temp5->c = 'N';
    found = found_ptr;
}

void Deletion(int val)
{
    if (mini == NULL)
        cout << "The heap is empty" << endl;
    else
    {

        Find(mini, val, 0);

        Extract_min();
        cout << "Key Deleted" << endl;
    }
}

void display()
{
    node *ptr = mini;
    if (ptr == NULL)
        cout << "The Heap is Empty" << endl;

    else
    {
        cout << "The root nodes of Heap are: " << endl;
        do
        {
            cout << ptr->key;
            ptr = ptr->right;
            if (ptr != mini)
            {
                cout << "-->";
            }
        } while (ptr != mini && ptr->right != NULL);
        cout << endl
             << "The heap has " << no_of_nodes << " nodes" << endl
             << endl;
    }
}

int main()
{
    cout << "Creating an initial heap" << endl;
    insertion(5);
    insertion(2);
    insertion(8);

    display();

    cout << "Extracting min" << endl;
    Extract_min();
    display();

    cout << "Decrease value of 8 to 7" << endl;
    Find(mini, 8, 7);
    display();

    cout << "Delete the node 7" << endl;
    Deletion(7);
    display();

    return 0;
}

// rabin karp

#include <bits/stdc++.h>
using namespace std;

// d is the number of characters in the input alphabet
#define d 256

// mod is a prime number used for modulo arithmetic
#define mod INT_MAX

void RabinKarpSearchPattern(string txt, string pat)
{
    int n = txt.size();
    int m = pat.size();

    int hashp = 0; // hash value for pattern
    int hasht = 0; // hash value for txt

    int h = 1;

    // h = d^(m-1)
    for(int i = 0; i < m - 1; i++)
        h = (h * d) % mod;

    for(int i = 0; i < m; i++){
        hashp = (d * hashp + pat[i]) % mod;
        hasht = (d * hasht + txt[i]) % mod;
    }

    // Slide the pattern over text one by one
    for(int i = 0; i <= n-m; i++){

        if(hashp == hasht){

            int j;

            for(j = 0; j < m; j++){
                if(txt[i + j] != pat[j]){
                    break;
                }
            }

            if(j == m)
                cout << "Pattern found at index " << i << endl;
        }

        // Calculate hash value for next window of text:
        if(i < n - m){
            hasht = (d*(hasht - txt[i]*h) + txt[i+m]) % mod;

            if(hasht < 0)
                hasht = (hasht + mod);
        }
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("../input.txt", "r", stdin);
        freopen("../output.txt", "w", stdout);
    #endif

    string str,pat;
    cin >> str >> pat;

    RabinKarpSearchPattern(str,pat);
}