import java.util.*;

public class SparseArray
{
    /** The number of rows and columns in the sparse array. */
    private int numRows;
    private int numCols;

    /** The list of entries representing the non-zero elements of the sparse array. Entries are stored in the
     * list in no particular order. Each non-zero element is represented by exactly one entry in the list.
     */
    private List<SparseArrayEntry> entries;

    /** Constructs an empty SparseArray. */
    public SparseArray()
    { entries = new ArrayList<SparseArrayEntry>(); }

    /** Returns the number of rows in the sparse array. */
    public int getNumRows()
    { return numRows; }

    /** Returns the number of columns in the sparse array. */
    public int getNumCols()
    { return numCols; }

    /** Returns the value of the element at row index row and column index col in the sparse array.
     * Precondition: 0  row < getNumRows()
     * 0  col < getNumCols()
     */
    public int getValueAt(int row, int col)
    {
        for(SparseArrayEntry e : entries)
        {
            if(e.getRow() == row && e.getCol() == col)
                return e.getValue();        
        }

        return 0;
    }

    /** Removes the column col from the sparse array.
     * Precondition: 0  col < getNumCols()
     */
    public void removeColumn(int col)
    {
        numCols--;

        for(int i = entries.size()-1; i >= 0; i--)
            if(entries.get(i).getCol() == col)
                entries.remove(i);

        for(int i = 0; i < entries.size(); i++)
            if(entries.get(i).getCol() >= col){
                SparseArrayEntry h = entries.get(i);
                SparseArrayEntry e = new SparseArrayEntry(h.getRow(),(h.getCol()-1),h.getValue());
                entries.set(i, e);
            }
    }

    // There may be instance variables, constructors, and methods that are not shown.
    
    public void addEntry(SparseArrayEntry e)
    {
        entries.add(e);
    }
    
    public String toString()
    {
        String r = "";
        for(SparseArrayEntry e : entries)
            r += e+"\n\n"; 
        return r;
    }
}