import java.util.*;

class Node {
    String key;
    String value;
    Node next;

    Node(String key, String value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

class SeparateChaining {
    private Node[] table;
    private int size;

    SeparateChaining(int capacity) {
        table = new Node[capacity];
        size = capacity;
    }

    private int hash(String key) {
        return Math.abs(key.hashCode()) % size;
    }

    public void put(String key, String value) {
        int index = hash(key);
        Node newNode = new Node(key, value);
        if (table[index] == null) {
            table[index] = newNode;
        } else {
            Node current = table[index];
            while (current.next != null) {
                if (current.key.equals(key)) {
                    current.value = value;
                    return;
                }
                current = current.next;
            }
            current.next = newNode;
        }
    }

    public String get(String key) {
        int index = hash(key);
        Node current = table[index];
        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null;
    }

    public void print() {
        System.out.println("Hash Table (Separate Chaining)");
        for (int i = 0; i < size; i++) {
            Node current = table[i];
            System.out.print("Index " + i + ": ");
            while (current != null) {
                System.out.print("(" + current.key + ", " + current.value + ") -> ");
                current = current.next;
            }
            System.out.println("null");
        }
    }
}

public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter size of hash table:");
        int size = scanner.nextInt();
        SeparateChaining separateChaining = new SeparateChaining(size);

        System.out.println("Enter key-value pairs (key value):");
        for (int i = 0; i < size; i++) {
            String key = scanner.next();
            String value = scanner.next();
            separateChaining.put(key, value);
        }

        separateChaining.print();

        System.out.println("Enter a key to retrieve its value:");
        String key = scanner.next();
        String retrievedValue = separateChaining.get(key);
        if (retrievedValue != null) {
            System.out.println("Value for key " + key + " is: " + retrievedValue);
        } else {
            System.out.println("Key not found.");
        }
        scanner.close();
    }
}