/*
Time limit: 1000ms
Memory limit: 256mb

---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF -1

typedef enum {INSERT = 1, GET, SUM, SIZE, ERROR_OP} OP;

const int hashTableSize = 2000003;
struct hashNode {
    int key;
    int value;
};

typedef struct hashNode* HashTable;

struct map {
    int size;
    long long sum;
    HashTable hashTable;
};

typedef struct map* MapADT;

// Hashing collision resolution: open addressing with double hashing
MapADT CreateMap() {
    MapADT m = (MapADT) malloc(sizeof(struct map));
    m->size = 0;
    m->hashTable = (struct hashNode*) malloc(hashTableSize * sizeof(struct hashNode));
    memset(m->hashTable, 0, hashTableSize * sizeof(struct hashNode)); 

    return m;
}

// The size of the hash table
// The number of key-value pairs in the hash table
int Size(MapADT myMap) {
    return myMap->size;
}

// The sum of all values in the hash table
long long Sum(MapADT myMap) {
    return myMap->sum;
}

// The first hash function
// Construct a suitable hash function for the key
int h1(int key)
{
    // WRITE YOUR CODE HERE

}

// The second hash function
// Construct a suitable hash function for the key
int h2(int key)
{
    // WRITE YOUR CODE HERE

}

// If the key already exists, update the value and sum
// If the key does not exist, insert the key-value pair into the hash table and update the size and sum
// You should probe the position using double hashing, i.e., h(key, i) = (h1(key) + i * h2(key)) % hashTableSize
void Insert(MapADT myMap, int key, int value) {
    // WRITE YOUR CODE HERE

}

// If the key is not found, return -1
// If the key is found, return the value
int Get(MapADT myMap, int key) {
    // WRITE YOUR CODE HERE

}

OP get_op() {
    char str[20];
    scanf("%s", str);
    if (strcmp(str, "Insert") == 0) {
        return INSERT;
    } else if (strcmp(str, "Get") == 0) {
        return GET;
    } else if (strcmp(str, "Sum") == 0) {
        return SUM;
    } else if (strcmp(str, "Size") == 0) {
        return SIZE;
    } else {
        return ERROR_OP;
    }
}

int main() 
{
    int n, key, value;
    MapADT myMap = CreateMap();
    scanf("%d", &n);

    for(int i = 0; i < n; i++)
    {
        switch (get_op()) {
            case INSERT:
                scanf(" %d%d", &key, &value);
                Insert(myMap, key, value);
                break;
            case GET:
                scanf(" %d", &key);
                int ans = Get(myMap, key);
                if (ans == -1) printf("NaN\n");
                else
                    printf("%d\n", Get(myMap, key));
                break;
            case SUM:
                scanf(" %d", &key);
                printf("%lld\n", Sum(myMap));
                break;
            case SIZE:
                printf("%d\n", Size(myMap));
                break;
            default:
                printf("Error Input\n");
        }
    }
    return 0;
}


---------------------------------------End of Code---------------------------------------

## [Unordered Map via Double Hashing]

You are tasked to implement an unordered map using a hash table with ​open addressing and ​double hashing for collision resolution. 

The map must support four operations:

The unordered map ADT has four operations:

1. Insert(key, value): Add the key-value pair to the map. If the key exists, update its value.

2. Get(key): Report the value associated with the key. Return 'NaN' if the key is absent.

3. Size(): Report the number of key-value pairs stored.

4. Sum(): Report the sum of all values in the map.

### Input
The first line contains one integer: N ($1\leq N \leq 10^6$)

The next n lines each describe an operation with integers:

 - Operation 1 (Insert): 'Insert k v'. Insert a key-value pair (k,v) into the map ($1\leq k,v \leq 10^6$). If the key already exists, update its value.

 - Operation 2 (Get): 'Get k'. Query the value of key $k$ ($1\leq k \leq 10^6$). If it does not have this key, report 'NaN'.

 - Operation 3 (Size): 'Size'. Report the number of key-value pairs stored.
 
 - Operation 4 (Sum): 'Sum'. Report the sum of all values in the map.

### Output

For each Get operation, output the value or 'NaN'.

For each Size or Sum operation, output a single integer.

### Example
**Input**
```
9
Insert 1 2
Insert 2 3
Size
Insert 3 5
Get 4
Sum
Insert 3 666
Sum
Get 3
```

**Output**
```
2
NaN
10
671
666
```