Given two vectors, compute their dot product. The dot product is the sum of the product of the corresponding components of the two vectors. For example, the dot product of [1,2,3] and [4,5,6] is 32 because 1*4+2*5+3*6 = 32.
We may represent a high-dimensional sparse vector using the following format:
dim1:value1 dim2:value2 dim3:value3 … dimN:valueN 0:0
where 0:0 denotes the end of the vector.
An example: The vector [0,5,0,0,9,0,0,33] is an eight-dimensional vector, which can be represented as
2:5 5:9 8:33 0:0
That is, we may omit all dimensions whose values are zero. Such a representation is compact and particularly suitable for high-dimensional sparse vectors.
Note that the dimensions may be presented in arbitrary order. For example, the above vector may also be expressed as
8:33 2:5 5:9 0:0
The input has two lines. Each line contains a vector of integer values represented in the sparse format. The usage of memory is limited to 32 MB. The dimension of the vector is no greater than 2 to the 31th power, and the N of dimN will not exceed 2 to the 20th power.
Note that the nonzero dimensions may be presented in arbitrary order. For example,
8:33 2:5 5:9 0:0
The output is the dot product of the two input vectors. The answer should be printed in one line with a newline character at the end.