using System;
using System.Collections.Generic;
using System.Text;
using System.Runtime.InteropServices;
using System.ComponentModel;
using System.Reflection;
 
public interface ITypedArray<T> : IEnumerable<T>
{
    int Length { get;}
    int Rank { get;}
    object SyncRoot { get;}
    bool IsFixedSize { get;}
    bool IsReadOnly { get;}
    bool IsSynchronized { get;}
    void CopyTo(ITypedArray<T> array, int index);
    bool Exists(T value);
    T Find(Predicate<T> predicate);
    void ForEach(Action<T> action);
    int GetLowerBound(int dimension);
    int GetUpperBound(int dimension);
    T GetValue(int index, params int[] indexes);
    void SetValue(T value, int index, params int[] indexes);
    int IndexOf(T value);
    void Initialize();
    int GetLength(int dimension);
    ITypedArray<T> Reverse();
    T[] ToSingleArray();
}
 
internal class CachedArrayItem<T>
{
    public CachedArrayItem(int index, ArrayItem<T> arrayItem)
    {
        Index = index;
        Item = arrayItem;
    }
    public CachedArrayItem()
        : this(-1, null)
    {
    }
    public int Index;
    public ArrayItem<T> Item;
}
 
public class ArrayItem<T>
{
    public ArrayItem(T data, ArrayItem<T> nextItem)
    {
        Data = data;
        NextItem = nextItem;
    }
    public ArrayItem()
        : this(default(T), null)
    {
    }
    public T Data;
    public ArrayItem<T> NextItem;
}
 
internal class ArrayEnumerator<T> : IEnumerator<T>, IDisposable
{
    protected readonly ArrayItem<T> m_firstItem;
    private ArrayItem<T> m_current;
    public bool IsInitialized;
    public ArrayEnumerator(ArrayItem<T> firstItem)
    {
        m_firstItem = firstItem;
        Reset();
    }
    public void Reset()
    {
        m_current = new ArrayItem<T>(default(T), m_firstItem);
        IsInitialized = false;
    }
    public bool MoveNext()
    {
        IsInitialized = true;
        m_current = m_current.NextItem;
        if (m_current == null) return false;
        return true;
    }
    public T Current
    {
        get
        {
            if (!IsInitialized) throw new InvalidOperationException("Enumeration has not started. Call MoveNext");
            return m_current.Data;
        }
    }
    object System.Collections.IEnumerator.Current
    {
        get
        {
            if (!IsInitialized) throw new InvalidOperationException("Enumeration has not started. Call MoveNext");
            return m_current;
        }
    }
    public void Dispose()
    {
        m_current = null;
    }
}
 
 
public class CachedSingleArray<T> : SingleArray<T>
{
    private readonly CachedArrayItem<T> cache;
    public CachedSingleArray(int length)
        :base(length)
    {
        cache = new CachedArrayItem<T>(0, firstItem);
    }
 
    public CachedSingleArray(T[] innerArray)
        :base(innerArray)
    {
        cache = new CachedArrayItem<T>(0, firstItem);
    }
 
    #region SingleArray<T> members
    public override T GetValue(int index, params int[] indexes)
    {
        if (indexes.Length != 0) throw new ArgumentException("Current array is one-dimensional");
        ArrayItem<T> currentItem = null;
        int startIndex = 0;
        if (index >= cache.Index)
        {
            currentItem = new ArrayItem<T>(default(T), cache.Item);
            startIndex = cache.Index;
        }
        else
            currentItem = new ArrayItem<T>(default(T), firstItem);
        for (int i = startIndex; i <= index; i++)
        {
            currentItem = currentItem.NextItem;
            if (currentItem == null) throw new IndexOutOfRangeException("Index of array element out of range");
        }
        cache.Index = index;
        return (cache.Item = currentItem).Data;
    }
    public override void SetValue(T value, int index, params int[] indexes)
    {
        if (indexes.Length != 0) throw new ArgumentException("Current array is one-dimensional");
        ArrayItem<T> currentItem = null;
        int startIndex = 0;
        if (index >= cache.Index)
        {
            currentItem = new ArrayItem<T>(default(T), cache.Item);
            startIndex = cache.Index;
        }
        else
            currentItem = new ArrayItem<T>(default(T), firstItem);
        for (int i = startIndex; i <= index; i++)
        {
            currentItem = currentItem.NextItem;
            if (currentItem == null) throw new IndexOutOfRangeException("Index of array element out of range");
        }
        cache.Index = index;
        (cache.Item = currentItem).Data = value;
    }
    #endregion
}
 
public class SingleArray<T> : ITypedArray<T>, ICloneable
{
    private int m_length;
    protected ArrayItem<T> firstItem;
    public SingleArray(int length)
    {
        m_length = length;
        firstItem = null;
        if (length > 0)
        {
            ArrayItem<T> tempItem = firstItem = new ArrayItem<T>();
            for (int i = 1; i < length; i++)
            {
                tempItem = tempItem.NextItem = new ArrayItem<T>();
            }
            tempItem.NextItem = null;
        }
    }
    public SingleArray(T[] innerArray)
    {
        m_length = innerArray.Length;
        ArrayItem<T> arrayItem = firstItem = new ArrayItem<T>();
        arrayItem.Data = innerArray[0];
        for (int i = 1; i < m_length; i++)
        {
            arrayItem = arrayItem.NextItem = new ArrayItem<T>();
            arrayItem.Data = innerArray[i];
        }
        arrayItem.NextItem = null;
    }
    public T this[int index]
    {
        get
        {
            return GetValue(index);
        }
        set
        {
            SetValue(value, index);
        }
    }
    public virtual int GetLowerBound()
    {
        return 0;
    }
    public virtual int GetUpperBound()
    {
        return m_length - 1;
    }
    #region ITypedArray<T> members
    public int Length
    {
        get { return m_length; }
    }
    public int Rank
    {
        get { return 1; }
    }
    public object SyncRoot
    {
        get { return firstItem; }
    }
    public bool IsFixedSize
    {
        get { return true; }
    }
    public bool IsReadOnly
    {
        get { return true; }
    }
    public bool IsSynchronized
    {
        get { return false; }
    }
    public void CopyTo(ITypedArray<T> sourceArray, int index)
    {
        ArrayItem<T> current = firstItem;
        int counter = index;
        do
        {
            sourceArray.SetValue(current.Data, counter++);
            current = current.NextItem;
        } while (current != null && counter < sourceArray.Length);
    }
    public bool Exists(T value)
    {
        return IndexOf(value) != -1;
    }
    public int IndexOf(T value)
    {
        ArrayItem<T> current = firstItem;
        int counter = 0;
        do
        {
            if (current.Data.Equals(value)) return counter;
            counter++;
            current = current.NextItem;
        } while (current != null);
        return -1;
    }
    public virtual T GetValue(int index, params int[] indexes)
    {
        if (indexes.Length != 0) throw new ArgumentException("Current array is one-dimensional");
        ArrayItem<T> currentItem = new ArrayItem<T>(default(T), firstItem);
        for (int i = 0; i <= index; i++)
        {
            currentItem = currentItem.NextItem;
            if (currentItem == null) throw new IndexOutOfRangeException("Index of array element out of range");
        }
        return currentItem.Data;
    }
    public virtual void SetValue(T value, int index, params int[] indexes)
    {
        if (indexes.Length != 0) throw new ArgumentException("Current array is one-dimensional");
        ArrayItem<T> currentItem = new ArrayItem<T>(default(T), firstItem);
        for (int i = 0; i <= index; i++)
        {
            currentItem = currentItem.NextItem;
            if (currentItem == null) throw new IndexOutOfRangeException("Index of array element out of range");
        }
        currentItem.Data = value;
    }
    public T Find(Predicate<T> predicate)
    {
        ArrayItem<T> current = firstItem;
        do
        {
            if (predicate(current.Data)) return current.Data;
            current = current.NextItem;
        } while (current != null);
        return default(T);
    }
    public void ForEach(Action<T> action)
    {
        ArrayItem<T> current = firstItem;
        do
        {
            action(current.Data);
            current = current.NextItem;
        } while (current != null);
    }
    public int GetLowerBound(int dimension)
    {
        if (dimension != 0) throw new ArgumentException("Current array is one-dimensional");
        return GetLowerBound();
    }
    public int GetUpperBound(int dimension)
    {
        if (dimension != 0) throw new ArgumentException("Current array is one-dimensional");
        return GetUpperBound();
    }
    public int GetLength(int dimension)
    {
        if (dimension != 0) throw new ArgumentException("Current array is one-dimensional");
        return m_length;
    }
    public void Initialize()
    {
        Initialize(default(T));
    }
    public ITypedArray<T> Reverse()
    {
        T[] buffer = ToSingleArray(false);
        Array.Reverse(buffer);
        return new SingleArray<T>(buffer);
    }
    public T[] ToSingleArray()
    {
        return ToSingleArray(false);
    }
    #endregion
    #region IEnumerable<T> members
    public IEnumerator<T> GetEnumerator()
    {
        return new ArrayEnumerator<T>(firstItem);
    }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return new ArrayEnumerator<T>(firstItem);
    }
    #endregion
    #region ICloneable members
    public object Clone()
    {
        return MemberwiseClone();
    }
    #endregion
    public void Initialize(T value)
    {
        ArrayItem<T> current = firstItem;
        do
        {
            current.Data = value;
            current = current.NextItem;
        } while (current != null);
    }
    public T[] ToSingleArray(bool isCopy)
    {
        T[] buffer = null;
        SingleArray<T> singleArray = null;
        if (isCopy) singleArray = (SingleArray<T>)Clone();
            else singleArray = this;
        ArrayItem<T> current = singleArray.firstItem;
        int counter = 0;
        do
        {
            buffer[counter++] = current.Data;
            current = current.NextItem;
        } while (current != null);
        return buffer;
    }
    public static T[] Concat(T[] self, params T[][] arrays)
    {
        List<T> result = new List<T>(self);
        foreach (T[] array in arrays)
        {
            result.AddRange(array);
        }
        return result.ToArray();
    }
    public static explicit operator SingleArray<T>(T[] innerArray)
    {
        return new SingleArray<T>(innerArray);
    }
    public static implicit operator T[](SingleArray<T> innerArray)
    {
        return innerArray.ToSingleArray(false);
    }
}
 
public class TypedArray<T> : ICloneable, ITypedArray<T>
{
    private readonly CachedSingleArray<int> indicies;
 
    protected readonly ArrayItem<T> firstItem;
 
    #region ITypedArray<T> members
    public virtual bool IsFixedSize
    {
        get { return true; }
    }
    public virtual bool IsReadOnly
    {
        get { return true; }
    }
    public virtual bool IsSynchronized
    {
        get { return false; }
    }
    public virtual int Length
    {
        get
        {
            ArrayItem<T> current = firstItem;
            int result = 0;
            while (current != null)
            {
                result++;
                current = current.NextItem;
            }
            return result;
        }
    }
    public Object SyncRoot
    {
        get
        {
            return firstItem;
        }
    }
    public int Rank
    {
        get { return indicies.Length; }
    }
    public void CopyTo(ITypedArray<T> sourceArray, int index)
    {
        ArrayItem<T> current = firstItem;
        int counter = index;
        do
        {
            sourceArray.SetValue(current.Data, counter++);
            current = current.NextItem;
        } while (current != null && counter < sourceArray.Length);
    }
    public bool Exists(T value)
    {
        return IndexOf(value) != -1;
    }
    public T Find(Predicate<T> predicate)
    {
        ArrayItem<T> current = firstItem;
        do
        {
            if (predicate(current.Data)) return current.Data;
            current = current.NextItem;
        } while (current != null);
        return default(T);
    }
    public ITypedArray<T> Reverse()
    {
        T[] buffer = ToSingleArray(true);
        Array.Reverse(buffer);
        return new TypedArray<T>(buffer);
    }
    public virtual int GetUpperBound(int dimension)
    {
        return GetLength(dimension) - 1;
    }
    public virtual int GetLowerBound(int dimension)
    {
        return 0;
    }
    public int IndexOf(T value)
    {
        ArrayItem<T> current = firstItem;
        int counter = 0;
        do
        {
            if (current.Data.Equals(value)) return counter;
            counter++;
            current = current.NextItem;
        } while (current != null);
        return -1;
    }
    public void SetValue(T value, int index, params int[] indexes)
    {
        this[index, indexes] = value;
    }
    public T GetValue(int index, params int[] indexes)
    {
        return this[index, indexes];
    }
    public void Initialize()
    {
        Initialize(default(T));
    }
    public int GetLength(int dimension)
    {
        return indicies[dimension];
    }
    public void ForEach(Action<T> action)
    {
        ArrayItem<T> current = firstItem;
        do
        {
            action(current.Data);
            current = current.NextItem;
        } while (current != null);
    }
    public T[] ToSingleArray()
    {
        return ToSingleArray(false);
    }
    #endregion
 
    #region IEnumerable<T> members
    public IEnumerator<T> GetEnumerator()
    {
        return new ArrayEnumerator<T>(firstItem);
    }
 
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return new ArrayEnumerator<T>(firstItem);
    }
    #endregion
 
    public virtual long LongLength
    {
        get
        {
            ArrayItem<T> current = firstItem;
            long result = 0;
            while (current != null)
            {
                result++;
                current = current.NextItem;
            }
            return result;
        }
    }
 
    public T[] ToSingleArray(bool isCopy)
    {
        T[] buffer = null;
        TypedArray<T> singleArray = null;
        if (isCopy) singleArray = (TypedArray<T>)Clone();
        else singleArray = this;
        ArrayItem<T> current = singleArray.firstItem;
        int counter = 0;
        do
        {
            buffer[counter++] = current.Data;
            current = current.NextItem;
        } while (current != null);
        return buffer;
    }
 
    public static implicit operator T[](TypedArray<T> typedArray)
    {
        return typedArray.ToSingleArray(false);
    }
 
    public static explicit operator TypedArray<T>(T[] managedArray)
    {
        return new TypedArray<T>(managedArray);
    }
 
    public TypedArray(int size, params int[] sizes)
    {
        indicies = new CachedSingleArray<int>(SingleArray<int>.Concat(new int[] { size }, sizes));
        foreach (int dimSize in sizes)
            size *= dimSize;
        firstItem = null;
        if (size > 0)
        {
            ArrayItem<T> tempItem = firstItem = new ArrayItem<T>();
            for (int i = 1; i < size; i++)
            {
                tempItem = tempItem.NextItem = new ArrayItem<T>();
            }
            tempItem.NextItem = null;
        }
    }
 
    public T this[int index, params int[] indexes]
    {
        get
        {
            return GetValueDirectly(GetAbsoluteIndex(index, indexes));
        }
        set
        {
            SetValueDirectly(value, GetAbsoluteIndex(index, indexes));
        }
    }
 
    public TypedArray(T[] array)    //Create alias array
    {
        //array = (T[])array.Clone(); //Create shallow copy
        indicies = new CachedSingleArray<int>(1);
        indicies[0] = array.Length;
        ArrayItem<T> tempItem = firstItem = new ArrayItem<T>();
        tempItem.Data = array[0];
        for (int i = 1; i < array.Length; i++)
        {
            tempItem = tempItem.NextItem = new ArrayItem<T>(array[i], null);
        }
    }
 
 
    public virtual void SetValueDirectly(T value, int absoluteIndex)
    {
        ArrayItem<T> currentItem = new ArrayItem<T>(default(T), firstItem);
        for (int i = 0; i <= absoluteIndex; i++)
        {
            currentItem = currentItem.NextItem;
            if (currentItem == null) throw new IndexOutOfRangeException("Index of array element out of range");
        }
        currentItem.Data = value;
    }
 
    public virtual T GetValueDirectly(int absoluteIndex)
    {
        ArrayItem<T> currentItem = new ArrayItem<T>(default(T), firstItem);
        for (int i = 0; i <= absoluteIndex; i++)
        {
            currentItem = currentItem.NextItem;
            if (currentItem == null) throw new IndexOutOfRangeException("Index of array element out of range");
        }
        return currentItem.Data;
    }
 
    public void SetValueDirectly(T value, long absoluteLongIndex)
    {
        ArrayItem<T> currentItem = new ArrayItem<T>(default(T), firstItem);
        for (long i = 0; i <= absoluteLongIndex; i++)
        {
            currentItem = currentItem.NextItem;
            if (currentItem == null) throw new IndexOutOfRangeException("Index of array element out of range");
        }
        currentItem.Data = value;
    }
 
    public T GetValueDirectly(long absoluteLongIndex)
    {
        ArrayItem<T> currentItem = new ArrayItem<T>(default(T), firstItem);
        for (long i = 0; i <= absoluteLongIndex; i++)
        {
            currentItem = currentItem.NextItem;
            if (currentItem == null) throw new IndexOutOfRangeException("Index of array element out of range");
        }
        return currentItem.Data;
    }
 
    public void Initialize(T value)
    {
        ArrayItem<T> current = firstItem;
        do
        {
            current.Data = value;
            current = current.NextItem;
        } while (current != null);
    }
 
    public void Initialize(T[] initValue)
    {
        ArrayItem<T> current = firstItem;
        int counter = 0;
        do
        {
            current.Data = initValue[counter++];
            current = current.NextItem;
        } while (current != null && counter < initValue.Length);
    }
 
    public static TypedArray<T> CreateAliasArray(T[] aliasArray)
    {
        return new TypedArray<T>(aliasArray);
    }
 
    public object Clone()
    {
        return this.MemberwiseClone();
    }
 
    public void CopyTo(TypedArray<T> sourceArray, long index)
    {
        ArrayItem<T> current = firstItem;
        long counter = index;
        do
        {
            sourceArray.SetValueDirectly(current.Data, counter++);
            current = current.NextItem;
        } while (current != null && counter < sourceArray.LongLength);
    }
 
 
 
    public long LongIndexOf(T value)
    {
        ArrayItem<T> current = firstItem;
        long counter = 0;
        do
        {
            if (current.Data.Equals(value)) return counter;
            counter++;
            current = current.NextItem;
        } while (current != null);
        return -1;
    }
 
    public int GetAbsoluteIndex(int index, params int[] indexes)
    {
        if (indexes.Length != indicies.Length - 1)
            throw new ArgumentException("The number of dimensions in the current array is not equal to the number of elements in indices");
        for (int i = 0; i < indexes.Length; i++)
        {
            if (indexes[i] >= indicies[i]) throw new IndexOutOfRangeException("Index of array element out of range");
            index += indexes[i] * indicies[i];
        }
        return index;
    }
 
    public int[] GetDimensionIndexes(int absoluteIndex)
    {
        int[] result = new int[indicies.Length];
        int length = Length;
        for (int i = result.Length - 1; i >=0 ; i--)
        {
            length /= indicies[i];
            int temp = absoluteIndex / length;
            absoluteIndex -= temp * length;
            result[i] = temp;
        }
        return result;
    }
}
 
public class CachedTypedArray<T> : TypedArray<T>
{
    private readonly CachedArrayItem<T> cache;
    public CachedTypedArray(int size, params int[] sizes)
        :base(size, sizes)
    {
        cache = new CachedArrayItem<T>(0, firstItem);
    }
 
    public CachedTypedArray(T[] innerArray)
        : base(innerArray)
    {
        cache = new CachedArrayItem<T>(0, firstItem);
    }
 
    public override T GetValueDirectly(int absoluteIndex)
    {
        ArrayItem<T> currentItem = null;
        int startIndex = 0;
        if (absoluteIndex >= cache.Index)
        {
            currentItem = new ArrayItem<T>(default(T), cache.Item);     //cache hit
            startIndex = cache.Index;
        }
        else
            currentItem = new ArrayItem<T>(default(T), firstItem);      //cache missing
        for (int i = startIndex; i <= absoluteIndex; i++)
        {
            currentItem = currentItem.NextItem;
            if (currentItem == null) throw new IndexOutOfRangeException("Index of array element out of range");
        }
        cache.Index = absoluteIndex;
        return (cache.Item = currentItem).Data;
    }
 
    public override void SetValueDirectly(T value, int absoluteIndex)
    {
        ArrayItem<T> currentItem = null;
        int startIndex = 0;
        if (absoluteIndex >= cache.Index)
        {
            currentItem = new ArrayItem<T>(default(T), cache.Item);     //cache hit
            startIndex = cache.Index;
        }
        else
            currentItem = new ArrayItem<T>(default(T), firstItem);      //cache missing
        for (int i = startIndex; i <= absoluteIndex; i++)
        {
            currentItem = currentItem.NextItem;
            if (currentItem == null) throw new IndexOutOfRangeException("Index of array element out of range");
        }
        cache.Index = absoluteIndex;
        (cache.Item = currentItem).Data = value;
    }
}