/*
   This code is hereby released to the public domain.
   ~aaaaaa123456789, 2015-04-02 (last updated 2015-04-07)
*/

using System.Collections;
using System.Collections.Generic;

public class UnlimitedMatrix<T> : IEnumerable, IEnumerable<long[]> {
  private object[] quadrants;
  private byte[] depths;
  private bool is_value_type;

  public UnlimitedMatrix () {
    quadrants = new object[4];
    depths = new byte[4];
    is_value_type = typeof(T).IsValueType;
  }

  private bool is_default (T value) {
    if (is_value_type) return value.Equals(default(T));
    return (object) value == null;
  }

  private int quadrant_for (ref long x, ref long y) {
    int result = 0;
    if (x < 0) {
      x = ~x;
      result ++;
    }
    if (y < 0) {
      y = ~y;
      result += 2;
    }
    return result;
  }

  private long max_index (byte depth) {
    if (depth >= 20) return 9223372036854775807;
    return (8L << (3 * depth)) - 1;
  }

  private byte depth_of (long index) {
    if (index < 0) return 255;
    byte current_depth = 0;
    while (index > 7) {
      current_depth ++;
      index >>= 3;
    }
    return current_depth;
  }

  private object retrieve (object array, byte depth, long x, long y) {
    if (depth > 0) {
      array = this.retrieve(array, (byte) (depth - 1), x >> 3, y >> 3);
      x &= 7;
      y &= 7;
    }
    if (array == null) return null;
    return ((object[]) array)[(x << 3) | y];
  }

  private void increase_depth (int quadrant, byte depth) {
    if (depth > 20) throw new System.ArgumentOutOfRangeException();
    if (this.quadrants[quadrant] == null) {
      this.quadrants[quadrant] = new T[64];
    }
    while (this.depths[quadrant] < depth) {
      object[] new_array = new object[65];
      new_array[0] = this.quadrants[quadrant];
      new_array[64] = 1;
      this.quadrants[quadrant] = new_array;
      this.depths[quadrant] ++;
    }
  }

  private byte[] get_coords (long x, long y, byte depth) {
    byte[] coords = new byte[21];
    byte current_depth;
    for (current_depth = 0; current_depth <= depth; current_depth ++) {
      coords[current_depth] = (byte) (((x & 7) << 3) + (y & 7));
      x >>= 3;
      y >>= 3;
    }
    return coords;
  }

  private bool is_empty (T[] array) {
    int p;
    for (p = 0; p < 64; p ++) if (!is_default(array[p])) return false;
    return true;
  }

  private void reduce (object[] locations, byte[] coords, int quadrant) {
    int depth = 0;
    object[] p;
    while (true) {
      if (locations[depth + 1] == null) {
        this.quadrants[quadrant] = null;
        this.depths[quadrant] = 0;
        return;
      }
      p = (object[]) locations[depth + 1];
      p[coords[depth]] = null;
      p[64] = (int) p[64] - 1;
      if (((int) p[64]) != 0) break;
      depth ++;
    }
    while (this.depths[quadrant] > 0) {
      p = (object[]) this.quadrants[quadrant];
      if (((int) p[64]) != 1) return;
      if (p[0] == null) return;
      this.quadrants[quadrant] = p[0];
      this.depths[quadrant] --;
    }
  }

  private void set (int quadrant, long x, long y, T value) {
    byte current_depth = this.depths[quadrant];
    byte[] coords = get_coords(x, y, current_depth);
    object location = this.quadrants[quadrant];
    object[] p;
    for (; current_depth > 0; current_depth --) {
      p = (object[]) location;
      if (p[coords[current_depth]] == null) {
        if (current_depth == 1)
          p[coords[current_depth]] = new T[64];
        else {
          object[] vr = new object[65];
          vr[64] = 0;
          p[coords[current_depth]] = vr;
        }
        p[64] = (int) p[64] + 1;
      }
      location = p[coords[current_depth]];
    }
    ((T[]) location)[coords[0]] = value;
  }

  public void unset (long x, long y) {
    if (is_default(this[x, y])) return;
    int quadrant = quadrant_for(ref x, ref y);
    byte current_depth = this.depths[quadrant];
    byte[] coords = get_coords(x, y, current_depth);
    object[] locations = new object[22];
    locations[current_depth] = this.quadrants[quadrant];
    while (current_depth > 0) {
      locations[current_depth - 1] = ((object[]) locations[current_depth])[coords[current_depth]];
      current_depth --;
    }
    ((T[]) locations[0])[coords[0]] = default(T);
    if (is_empty((T[]) locations[0])) this.reduce(locations, coords, quadrant);
  }

  public T this [long x, long y] {
    get {
      int quad = quadrant_for(ref x, ref y);
      if (this.quadrants[quad] == null) return default(T);
      long rv = max_index(this.depths[quad]);
      if ((x > rv) || (y > rv)) return default(T);
      T[] array;
      if (this.depths[quad] > 0) {
        array = (T[]) this.retrieve(this.quadrants[quad], (byte) (this.depths[quad] - 1), x >> 3, y >> 3);
        if (array == null) return default(T);
        x &= 7;
        y &= 7;
      } else {
        array = (T[]) this.quadrants[quad];
      }
      return array[(x << 3) | y];
    }
    set {
      if (is_default(value)) {
        this.unset(x, y);
        return;
      }
      int quad = quadrant_for(ref x, ref y);
      byte depth = depth_of(x);
      byte t = depth_of(y);
      if (t > depth) depth = t;
      if ((this.quadrants[quad] == null) || (this.depths[quad] < depth))
        this.increase_depth(quad, depth);
      this.set(quad, x, y, value);
    }
  }

  public T this [int x, int y] {
    set {
      this[(long) x, (long) y] = value;
    }
    get {
      return this[(long) x, (long) y];
    }
  }

  public void clear () {
    this.quadrants = new object[4];
    this.depths = new byte[4];
    System.GC.Collect();
  }

  private IEnumerable<long[]> enumerate_direct (T[] array, bool ascending, long x, long y, int quadrant) {
    x <<= 3;
    y <<= 3;
    int pos, index;
    long effectiveX, effectiveY;
    for (pos = 0; pos < 64; pos ++) {
      index = (pos & 1) | ((pos >> 1) & 2) | ((pos >> 2) & 4) | ((((pos >> 1) & 1) | ((pos >> 2) & 2) | ((pos >> 3) & 4)) << 3);
      if (!ascending) index ^= 63;
      if (is_default(array[index])) continue;
      effectiveX = x + (index >> 3);
      effectiveY = y + (index & 7);
      if ((quadrant & 1) == 1) effectiveX = ~effectiveX;
      if ((quadrant & 2) == 2) effectiveY = ~effectiveY;
      yield return new long[] {effectiveX, effectiveY};
    }
  }

  private IEnumerable<long[]> enumerate_indirect (object[] array, bool ascending, byte depth, long x, long y, int quadrant) {
    depth --;
    x <<= 3;
    y <<= 3;
    int pos, index;
    for (pos = 0; pos < 64; pos ++) {
      index = (pos & 1) | ((pos >> 1) & 2) | ((pos >> 2) & 4) | ((((pos >> 1) & 1) | ((pos >> 2) & 2) | ((pos >> 3) & 4)) << 3);
      if (!ascending) index ^= 63;
      if (array[index] == null) continue;
      if (depth == 0)
        foreach (long[] current in enumerate_direct((T[]) array[index], ascending, x + (index >> 3), y + (index & 7), quadrant))
          yield return current;
      else
        foreach (long[] current in enumerate_indirect(
          (object[]) array[index],
          ascending,
          depth,
          x + (index >> 3),
          y + (index & 7),
          quadrant
        )) yield return current;
    }
  }

  private IEnumerable<long[]> enumerate_quadrant (int quadrant, bool ascending) {
    if (quadrants[quadrant] == null) yield break;
    if (depths[quadrant] == 0) {
      foreach (long[] current in enumerate_direct(
        (T[]) quadrants[quadrant], ascending, 0, 0, quadrant
      )) yield return current;
      yield break;
    }
    foreach (long[] current in enumerate_indirect(
      (object[]) quadrants[quadrant], ascending, depths[quadrant], 0, 0, quadrant
    )) yield return current;
  }

  public IEnumerator<long[]> GetEnumerator () {
    foreach (long[] current in enumerate_quadrant(1, false)) yield return current;
    foreach (long[] current in enumerate_quadrant(0, true)) yield return current;
    foreach (long[] current in enumerate_quadrant(3, false)) yield return current;
    foreach (long[] current in enumerate_quadrant(2, true)) yield return current;
  }

  IEnumerator IEnumerable.GetEnumerator () {
    return GetEnumerator();
  }
}