Intersection of Dictionaries

Given several dictionaries, your task is to compute their intersection. The intersection of dictionaries is defined as the set of key-value pairs (k, v) that appear in every dictionary. More formally, if we have dictionaries \(D_1, D_2, \dots, D_n\), then the intersection is given by:

$$\bigcap_{i=1}^n D_i = \{ (k,v) \mid \forall i \ (k \in D_i \text{ and } D_i[k] = v) \}.$$

If there is no common key-value pair, output an empty dictionary {}. The input is taken from standard input and the result should be printed in JSON format with keys sorted in lexicographical order.

inputFormat

The input begins with an integer d representing the number of dictionaries. For each dictionary, the first line contains an integer n (the number of key-value pairs). The next n lines each contain a string and an integer separated by a space, representing a key and its corresponding value.

outputFormat

Output a single line containing the intersection dictionary in JSON format. The keys must be sorted in lexicographical order. If no common key-value pair exists, output {}.

3
2
a 1
b 2
2
a 1
c 3
3
a 1
b 2
d 4

{"a": 1}