using System;
using System.Collections.Generic;
using System.Numerics;
using System.Text;

namespace Sandbox
{
    // Inspired by https://arxiv.org/pdf/0708.3721.pdf
    // This uses Taylor series for atan, sin, cos to compute safe intervals within which their exact values lie.
    // Note that the C# syntax is old-style so that it will be compatible with old versions of Mono.
    class BigDecimalInterval
    {
        static readonly BigInteger Precision = BigInteger.Pow(2, 250);

        internal static void Main()
        {
            // Outputs in B-file format going as far as permitted by the specified value of Precision.
            BigDecimalInterval x = 1;
            Console.WriteLine("{0} {1}", 0, 1);
            for (int i = 1; true; i++)
            {
                // Tan is fine for -pi/2 to pi/2.
                while (x.Upper > Pi.Lower / 2) x -= Pi;
                while (x.Lower < Pi.Lower / -2) x += Pi;

                x = Tan(x);

                long nearest = (long)Math.Round(x.Upper);
                var ceil = nearest + new Rational(1, 2);
                var floor = nearest - new Rational(1, 2);
                if (x.Lower <= floor || x.Upper >= ceil) break;

                Console.WriteLine("{0} {1}", i, nearest);
            }
        }

        private BigInteger _Precision { get; set; }
        public Rational Lower { get; private set; }
        public Rational Upper { get; private set; }

        private BigDecimalInterval(Rational r, BigInteger precision)
        {
            _Precision = precision;
            if (r.Denom <= precision)
            {
                Lower = Upper = r;
                return;
            }

            // Note: I experimented with preferring continuants over treating the precision as a desired denominator,
            // and the performance loss was quite considerable.
            r = r * precision;
            if (r.Denom == 1)
            {
                Lower = Upper = r;
            }
            else if (r.Num > 0)
            {
                var floor = r.Num / r.Denom;
                Lower = new Rational(floor, precision);
                Upper = new Rational(floor + 1, precision);
            }
            else
            {
                var ceil = -((-r.Num) / r.Denom);
                Lower = new Rational(ceil - 1, precision);
                Upper = new Rational(ceil, precision);
            }
        }

        private BigDecimalInterval(Rational lower, Rational upper, BigInteger precision)
        {
            if (lower > upper) throw new ArgumentOutOfRangeException();

            _Precision = precision;
            Lower = new BigDecimalInterval(lower, precision).Lower;
            Upper = new BigDecimalInterval(upper, precision).Upper;
        }

        public BigDecimalInterval(Rational r) : this(r, Precision) { }

        public BigDecimalInterval(Rational lower, Rational upper) : this(lower, upper, Precision) { }

        #region Operators

        public static implicit operator BigDecimalInterval(int r) { return new BigDecimalInterval(r); }

        public static BigDecimalInterval operator -(BigDecimalInterval a) { return new BigDecimalInterval(-a.Upper, -a.Lower, a._Precision); }

        public static BigDecimalInterval operator +(BigDecimalInterval a, BigDecimalInterval b) { return new BigDecimalInterval(a.Lower + b.Lower, a.Upper + b.Upper, Max(a._Precision, b._Precision)); }
        public static BigDecimalInterval operator -(BigDecimalInterval a, BigDecimalInterval b) { return new BigDecimalInterval(a.Lower - b.Upper, a.Upper - b.Lower, Max(a._Precision, b._Precision)); }

        // These two methods assume a > 0
        public static BigDecimalInterval operator *(int a, BigDecimalInterval b) { return new BigDecimalInterval(a * b.Lower, a * b.Upper, b._Precision); }
        public static BigDecimalInterval operator /(BigDecimalInterval a, int b) { return new BigDecimalInterval(a.Lower / b, a.Upper / b, a._Precision); }

        private static BigInteger Max(BigInteger a, BigInteger b) { return a > b ? a : b; }

        #endregion

        #region Trigonometry

        public static BigDecimalInterval Atan(Rational x)
        {
            // atan(x) = \sum_{i=0}^\infty (-1)^i x^{2i+1} / (2i+1)
            Rational lower = 0;
            Rational upper = x;

            var intermediatePrecision = Precision * Precision;
            var epsilon = new Rational(1, intermediatePrecision);

            BigDecimalInterval sum = 0;
            BigDecimalInterval term = new BigDecimalInterval(x, intermediatePrecision);
            var x2 = x * x;
            for (int i = 0; true; i++)
            {
                sum += term / (2 * i + 1);
                term = new BigDecimalInterval(term.Upper * -x2, term.Lower * -x2, intermediatePrecision);

                if (i % 2 == 0) upper = sum.Upper;
                else lower = sum.Lower;

                if (term.Lower.Abs() <= epsilon && term.Upper.Abs() <= epsilon) break;
            }

            return new BigDecimalInterval(lower, upper, Precision);
        }

        private static readonly BigDecimalInterval Pi = 16 * Atan(new Rational(1, 5)) - 4 * Atan(new Rational(1, 239));

        private static BigDecimalInterval Sin(Rational x)
        {
            if (x < 0) return -Sin(-x);

            // sin(x) = sum_{i=0}^\infty (-1)^{i} x^{2i+1} / (2i+1)!
            Rational lower = -1;
            Rational upper = 1;

            var intermediatePrecision = Precision * Precision;
            var epsilon = new Rational(1, intermediatePrecision);

            BigDecimalInterval term = new BigDecimalInterval(x, intermediatePrecision);
            BigDecimalInterval sum = term;
            var x2 = x * x;
            for (int i = 1; true; i++)
            {
                var m = x2 / -((2 * i) * (2 * i + 1));
                term = new BigDecimalInterval(term.Upper * m, term.Lower * m, intermediatePrecision);
                sum += term;

                if (i % 2 == 0) upper = sum.Upper;
                else lower = sum.Lower;

                if (term.Lower.Abs() <= epsilon && term.Upper.Abs() <= epsilon) break;
            }

            return new BigDecimalInterval(lower, upper, Precision);
        }

        private static BigDecimalInterval Cos(Rational x)
        {
            if (x < 0) x = -x;

            // cos(x) = sum_{i=0}^\infty (-1)^i x^{2i} / (2i)!
            Rational lower = -1;
            Rational upper = 1;

            var intermediatePrecision = Precision * Precision;
            var epsilon = new Rational(1, intermediatePrecision);

            BigDecimalInterval term = new BigDecimalInterval(1, intermediatePrecision);
            BigDecimalInterval sum = term;
            var x2 = x * x;
            for (int i = 1; true; i++)
            {
                var m = x2 / -((2 * i - 1) * (2 * i));
                term = new BigDecimalInterval(term.Upper * m, term.Lower * m, intermediatePrecision);
                sum += term;

                if (i % 2 == 0) upper = sum.Upper;
                else lower = sum.Lower;

                if (term.Lower.Abs() <= epsilon && term.Upper.Abs() <= epsilon) break;
            }

            return new BigDecimalInterval(lower, upper, Precision);
        }

        public static BigDecimalInterval Tan(BigDecimalInterval x)
        {
            if (x.Upper < 0) return -Tan(-x);

            if (x.Lower >= Pi.Lower / -2 && x.Upper <= Pi.Lower / 2)
            {
                var lb = Sin(x.Lower).Lower / Cos(x.Lower).Upper;
                var ub = Sin(x.Upper).Upper / Cos(x.Upper).Lower;
                return new BigDecimalInterval(lb, ub);
            }

            throw new ArgumentOutOfRangeException("x");
        }

        #endregion
    }

    public class Rational
    {
        public Rational(BigInteger num, BigInteger denom)
        {
            if (denom.IsZero) throw new ArgumentOutOfRangeException("denom");

            if (denom < 0) { num = -num; denom = -denom; }

            var g = _Gcd(num, denom);
            Num = num / g;
            Denom = denom / g;
        }

        public BigInteger Num { get; private set; }
        public BigInteger Denom { get; private set; }

        public Rational Abs() { return Num < 0 ? -this : this; }

        public override int GetHashCode() { return Num.GetHashCode() * 37 + Denom.GetHashCode(); }
        public override bool Equals(object obj) { return obj is Rational && (this == (Rational)obj); }

        public static implicit operator Rational(long i) { return new Rational(i, 1); }
        public static implicit operator Rational(BigInteger i) { return new Rational(i, 1); }

        public static implicit operator double(Rational r) { return (double)r.Num / (double)r.Denom; }

        public static Rational operator -(Rational a) { return new Rational(-a.Num, a.Denom); }

        public static Rational operator +(Rational a, Rational b) { return new Rational(a.Num * b.Denom + a.Denom * b.Num, a.Denom * b.Denom); }
        public static Rational operator -(Rational a, Rational b) { return new Rational(a.Num * b.Denom - a.Denom * b.Num, a.Denom * b.Denom); }
        public static Rational operator *(Rational a, Rational b) { return new Rational(a.Num * b.Num, a.Denom * b.Denom); }
        public static Rational operator /(Rational a, Rational b) { return new Rational(a.Num * b.Denom, a.Denom * b.Num); }

        public static bool operator <(Rational a, Rational b) { return a.Num * b.Denom < a.Denom * b.Num; }
        public static bool operator >(Rational a, Rational b) { return a.Num * b.Denom > a.Denom * b.Num; }

        private static BigInteger _Gcd(BigInteger a, BigInteger b)
        {
            if (a < 0) a = -a;
            if (b < 0) b = -b;
            while (!a.IsZero)
            {
                var tmp = b % a;
                b = a;
                a = tmp;
            }
            return b;
        }
    }
}