#include <iostream>

using namespace std;

// {1, 4, 5}   <--- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0} N n
// {6, -2, 0}  <--- {2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1} N m

// SparseVector
struct SparseVector {
    vector<pair<int,int>> vals; // first:= index , second:= value
};

// Run-time complexity O(N)
// Memory complexity O(1)

int DotProduct(const vector<int>& v1, const vector<int>& v2) {
    int ans = 0;
    for (int i = 0; i < v1.size(); ++i) {
        if (v1[i] != 0 && v2[i] != 0)
            ans += v1[i]*v2[i];
    }
    return ans;
}

// (1, 5, 4, 3)  (4, 3, 7 ,8)

// ans = 3*3 + 4*4 + 8*8

// (1, 3, 4, 8)
//  ^
// (3, 4, 7 ,8)
//  ^
// (

// Run-time complexity O(m*n)
// Memory complexity O(1)

int SparseDotProduct(const SparseVector& v1, const SparseVector& v2) {
    int ans = 0;
    for (int i = 0; i < v1.vals.size(); ++i) {
        for (int j = 0; j < v2.vals.size(); ++j) {
            if (v1.vals[i].first == v2.vals[i].first)
                ans += v1.vals[i].second * v2.vals[i].second;
        }
    }
    return ans;
}

// (1, 3, 4, 5)  (3, 4, 7 ,8)

// (1, 3, 4, 5)
//  ^
// (3, 4, 7 ,8)
//  ^
// ans = 3*3 + 4*4

// Run-time complexity O(m + n)
// Memory complexity O(1)

int SparseDotProduct(const SparseVector& v1, const SparseVector& v2) {
    int ans = 0;
    int i1 = 0;
    int i2 = 0;
    while (i1 < v1.vals.size() && i2 < v2.vals.size()) {
        if (v1.vals[i1].first == v2.vals[i2].first)
            ans += v1.vals[i1++].second * v2.vals[i2++].second;
        else {
            if (v1.vals[i1].first < v2.vals[i2].first)
                ++i1;
            else
                ++i2;
        }
    }
    return ans;
}

// SparseVector
struct SparseVector {
    unordered_map<int, int> vals; // first:= index , second:= value
};

// O(min(n, m))
int SparseDotProduct(const SparseVector& v1, const SparseVector& v2) {

    if (v1.vals.size() > v2.vals.size())
        return SparseDotProduct(v2, v1);

    int ans = 0;
    for (auto it = v1.vals.begin(); it != v1.vals.end(); ++it) {
        if (v2.vals.count(it->first) == 1)
            ans += it->second * v2.vals[it->first];
    }

    return ans;
}


// [x]
// [ ]
// [y]
// [ ]

// hash_function(input)  ->  index e [0, table_size)
//     return input % table_size;

// unordered_map<int, int> hash;
// hash[5] = 10;
// hash_function(5) -> 5, hash.internal_table[5] = 10;

// hash[70000] = 8;
// hash_function(70000) -> 8, hash.internal_table[8] = 8;

// hash[5443] = 3;
// hash_function(5443) -> 5 // collision! -> 6; hash.internal_table[6] = 3

int main(){

}