Copy

// -----------------------------------------------------------------------------
// Fast I/O                                                                   C#
// -----------------------------------------------------------------------------
// FIO()
// FIO(Stream stdin)
// void Close()
// void Dispose()
// string ReadToEnd()
// string ReadLine()
// string ReadToken()
// int ReadInt()
// long ReadLong()
// decimal ReadDecimal()
// double ReadDouble()
// int[] ReadIntArr(int n)
// long[] ReadLongArr(int n)
// decimal[] ReadDecimalArr(int n)
// double[] ReadDoubleArr(int n)
// void Write(string value)
// void WriteLine(string value)
// -----------------------------------------------------------------------------
public class FIO : IDisposable
{
    const int BUFFER_SIZE = 4096;
    byte[] byteBuffer;
    char[] charBuffer;
    int byteBufferSize;
    int charBufferSize;
    int charPos;
    int charLen;
    int byteLen;
    Stream stm = null;
    StreamWriter sw = null;
    public FIO()
    {
        stm = Console.OpenStandardInput();
        sw = new StreamWriter(Console.OpenStandardOutput());
        Init();
    }
    public FIO(Stream stdin)
    {
        stm = stdin;
        sw = new StreamWriter(Console.OpenStandardOutput());
        Init();
    }
    public void Close()
    {
        Dispose();
    }
    public void Dispose()
    {
        try
        {
            stm.Close();
            sw.Dispose();
        }
        finally
        {
            if (stm != null)
            {
                stm = null;
                byteBuffer = null;
                charBuffer = null;
                charPos = 0;
                charLen = 0;
            }
        }
    }
    void Init()
    {
        byteBufferSize = BUFFER_SIZE;
        byteBuffer = new byte[byteBufferSize];
        charBufferSize = Encoding.UTF8.GetMaxCharCount(byteBufferSize);
        charBuffer = new char[charBufferSize];
        charPos = 0;
        charLen = 0;
        byteLen = 0;
    }
    int ReadBuffer()
    {
        charLen = 0;
        charPos = 0;
        byteLen = 0;
        do
        {
            byteLen = stm.Read(byteBuffer, 0, byteBuffer.Length);
            if (byteLen == 0) return charLen;
            charLen += Encoding.UTF8.GetChars(byteBuffer, 0, byteLen,
                                              charBuffer, charLen);
        } while (charLen == 0);
        return charLen;
    }
    public string ReadToEnd()
    {
        StringBuilder sb = new StringBuilder(charLen - charPos);
        do
        {
            sb.Append(charBuffer, charPos, charLen - charPos);
            charPos = charLen;
            ReadBuffer();
        } while (charLen > 0);
        return sb.ToString();
    }
    public string ReadLine()
    {
        if (charPos == charLen)
        {
            if (ReadBuffer() == 0) return null;
        }
        StringBuilder sb = null;
        do
        {
            int i = charPos;
            do
            {
                char ch = charBuffer[i];
                if (ch == '\r' || ch == '\n')
                {
                    string s;
                    if (sb != null)
                    {
                        sb.Append(charBuffer, charPos, i - charPos);
                        s = sb.ToString();
                    }
                    else
                    {
                        s = new string(charBuffer, charPos, i - charPos);
                    }
                    charPos = i + 1;
                    if (ch == '\r' && (charPos < charLen || ReadBuffer() > 0))
                    {
                        if (charBuffer[charPos] == '\n') charPos++;
                    }
                    return s;
                }
                i++;
            } while (i < charLen);
            i = charLen - charPos;
            if (sb == null) sb = new StringBuilder(i + 80);
            sb.Append(charBuffer, charPos, i);
        } while (ReadBuffer() > 0);
        return sb.ToString();
    }
    public string ReadToken()
    {
        if (charPos == charLen)
        {
            if (ReadBuffer() == 0) return null;
        }
        StringBuilder sb = null;
        do
        {
            int i = charPos;
            do
            {
                char ch = charBuffer[i];
                if (ch == '\r' || ch == '\n' || ch == ' ')
                {
                    string s;
                    if (sb != null)
                    {
                        sb.Append(charBuffer, charPos, i - charPos);
                        s = sb.ToString();
                    }
                    else
                    {
                        s = new string(charBuffer, charPos, i - charPos);
                    }
                    charPos = i + 1;
                    if (ch == '\r' && (charPos < charLen || ReadBuffer() > 0))
                    {
                        if (charBuffer[charPos] == '\n' ||
                            charBuffer[charPos] == ' ') charPos++;
                    }
                    if (!string.IsNullOrEmpty(s)) return s;
                    i = charPos;
                }
                i++;
            } while (i < charLen);
            i = charLen - charPos;
            if (sb == null) sb = new StringBuilder(i + 80);
            sb.Append(charBuffer, charPos, i);
        } while (ReadBuffer() > 0);
        return sb.ToString();
    }
    long ReadLongToken()
    {
        long y = 0;
        bool neg = false;
        bool none = true;
        if (charPos == charLen)
        {
            if (ReadBuffer() == 0) return 0;
        }
        do
        {
            int i = charPos;
            do
            {
                char ch = charBuffer[i];
                if (ch == '\r' || ch == '\n' || ch == ' ')
                {
                    for (int j = 0; j < (i - charPos); j++)
                    {
                        if (j == 0 && charBuffer[j + charPos] == '-') neg = true;
                        else y = y * 10 + (charBuffer[j + charPos] - '0');
                        none = false;
                    }
                    charPos = i + 1;
                    if (ch == '\r' && (charPos < charLen || ReadBuffer() > 0))
                    {
                        if (charBuffer[charPos] == '\n' ||
                            charBuffer[charPos] == ' ') charPos++;
                    }
                    if (!none) return neg ? -y : y;
                    i = charPos;
                }
                i++;
            } while (i < charLen);
            i = charLen - charPos;
            for (int j = 0; j < i; j++)
            {
                if (j == 0 && charBuffer[j + charPos] == '-') neg = true;
                else y = y * 10 + (charBuffer[j + charPos] - '0');
                none = false;
            }
        } while (ReadBuffer() > 0);
        return neg ? -y : y;
    }
    public int ReadInt()
    {
        return (int)ReadLongToken();
    }
    public long ReadLong()
    {
        return ReadLongToken();
    }
    public decimal ReadDecimal()
    {
        string s = ReadToken();
        long n = 0;
        int decimalPosition = s.Length;
        for (int k = 0; k < s.Length; k++)
        {
            char c = s[k];
            if (c == '.')
                decimalPosition = k + 1;
            else
                n = (n * 10) + (c - '0');
        }
        return new decimal((int)n, (int)(n >> 32), 0, false,
                           (byte)(s.Length - decimalPosition));
    }
    public double ReadDouble()
    {
        return (double)ReadDecimal();
    }
    public int[] ReadIntArr(int n)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = (int)ReadLongToken();
        return arr;
    }
    public long[] ReadLongArr(int n)
    {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) arr[i] = ReadLongToken();
        return arr;
    }
    public decimal[] ReadDecimalArr(int n)
    {
        decimal[] arr = new decimal[n];
        for (int i = 0; i < n; i++) arr[i] = ReadDecimal();
        return arr;
    }
    public double[] ReadDoubleArr(int n)
    {
        double[] arr = new double[n];
        for (int i = 0; i < n; i++) arr[i] = ReadDouble();
        return arr;
    }
    public void Write(string value)
    {
        sw.Write(value);
    }
    public void WriteLine(string value)
    {
        sw.WriteLine(value);
    }
}
// -----------------------------------------------------------------------------