** Next:** Line Drawing
**Up:** No Title
** Previous:** Sequence of Differences

A vector is a one-dimensional array of elements. The natural C++
implementation of a vector is as a one-dimensional array. However,
in many applications, the elements of a vector have mostly zero values.
Such a vector is said to be sparse. It is inefficient to use a
one-dimensional array to store a sparse vector. It is also inefficient
to add elements whose values are zero in forming sums of sparse vectors.
Consequently, we should choose a different representation.

One possibility is to represent the elements of a sparse vector as a linked
list of nodes, each of which contains an integer index, a numerical value,
and a pointer to the next node.
Generally, the entries of the list will correspond to the non-zero elements
of the vector in order, with each entry containing the index and value for
that entry. (This restriction may be violated if a zero value is explicitly
assigned to an element).

Your goal is to write a program to add pairs of sparse vectors,
creating new sparse vectors. The results of addition should not
include any elements whose values are zero. You should then
print the resulting vectors with elements in ascending order of
index (from smallest index to largest).

The input will be several pairs of sparse vectors, with each
vector on a separate line. Each sparse vector will consist
of a number of index-value pairs, where the first number in
each pair is an integer representing the index (location), and the
second number is a floating-point number representing the actual
value. You may assume all index locations are non-negative.
Elements will be entered in ascending order of index.
The list of vectors is terminated by a line containing only -1.

The output will be sparse vectors representing the sum
of each pair of input vectors, each on a separate line.
Vector elements should appear as pairs of indices and values,
separated by a comma and a blank and enclosed in square braces.
Vectors should appear as lists of elements separated by commas.
The vector elements must be printed in ascending order of index.
Vectors with no elements should appear as the string "empty vector".

**Input:**

3 1.0 2500 6.3 5000 10.0 60000 5.7
1 7.5 3 5.7 2500 -6.3
10 0.0
15000 6.7
100 -1.0
100 1.0
-1

**Output:**

[1, 7.5], [3, 6.7], [5000, 10], [60000, 5.7]
[15000, 6.7]
empty vector

## Test data used in judging

** Next:** Line Drawing
**Up:** No Title
** Previous:** Sequence of Differences
*Chau-Wen Tseng *

Mon Mar 15 13:58:05 EST 1999