// Compiled with: g++ -Wall -std=c++14 -pthread


#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
};

// O(N)
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;
}

// O(n*m)  {4, 3, 7, 8}
// O(1)    {1, 5, 4, 3}
// (1, 5, 4, 3)  (4, 3, 7 ,8)

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

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

// O(m + n)

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;
}

// O(m + n)
int IntersectionSparseDotProduct(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 SparseVector2 {
    unordered_map<int, int> vals; // first:= index , second:= value
};

// O(min(n, m))
int HashSparseDotProduct(const SparseVector2& v1, const SparseVector2& v2) {

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

    int ans = 0;

    // for (auto& pair: v1.vals)
    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(){

}