public_key_crypto_4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Cryptography\n",
    "\n",
    "## Public key cryptography - Part 4\n",
    "\n",
    "# RSA Signatures, RSA Encryption, Factoring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Formuation of propositions, lemmas, definitions comes from:\n",
    "**Introduction to modern cryptography** by *Jonathan Katz* and *Yehuda Lindell*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "To see the notebook as a slide-show, use [RISE](https://rise.readthedocs.io/en/stable/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import math\n",
    "import random\n",
    "from sympy import randprime, isprime, Mod"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Agenda"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### RSA\n",
    "\n",
    "* Encryption (OAEP)\n",
    "* Signatures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Factoring algorithms\n",
    "\n",
    "* trial division\n",
    "* p-1 method\n",
    "* fermat's factoring method\n",
    "* QS - quadratic sieve \n",
    "* ECM - elliptic curve method\n",
    "* NFS - number field sieve"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Proposition 7.2** Let $a, b$ be positive integers. Then there exists integers $X, Y$ such that $Xa + Yb = \\gcd(a, b)$. \n",
    "\n",
    "Furthermore, $\\gcd(a, b)$ is the smallest positive integer that can be expressed in this way."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def egcd(a, b):\n",
    "    if a == 0:\n",
    "        return (b, 0, 1)\n",
    "    else:\n",
    "        g, y, x = egcd(b % a, a)\n",
    "        return (g, x - (b // a) * y, y)\n",
    "\n",
    "def modinv(a, m):\n",
    "    g, x, y = egcd(a, m)\n",
    "    if g != 1:\n",
    "        raise Exception('modular inverse does not exist')\n",
    "    else:\n",
    "        return x % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "19\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = 10\n",
    "b = 21\n",
    "\n",
    "gcd, x, y = egcd(a, b)\n",
    "\n",
    "print(gcd)\n",
    "\n",
    "a_min_1 = modinv(a, b)\n",
    "print(a_min_1)\n",
    "a_min_1 * 10 % b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(a, \"*\", x, \"+\", b, \"*\", y, \"=\", math.gcd(a,b))\n",
    "a * x + b * y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "If for $b$ there exists an integer $b^{-1}$ such that $b b^{-1} = 1 \\bmod N$ then we call:\n",
    "\n",
    "* $b$ invertible\n",
    "\n",
    "* $b^{-1}$ modular inverse of $b$ modulo $N$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Proposition 7.7** Let $a, N$ be integers, with $N > 1$. Then $a$ is invertible modulo $N$ if and only if $\\gcd(a, N) = 1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Definition 7.9** A group is a set $\\mathbf{G}$ along with a binary operation $\\oplus$ for which the following conditions hold:\n",
    "\n",
    "* (Closure:) For all $g, h \\in \\mathbf{G}$, $g \\oplus h \\in \\mathbf{G}$\n",
    "\n",
    "* (Existance of an Identity:) There exists an **identity** $e \\in \\mathbf{G}$ such that for all $g \\in \\mathcal{G}$, $e \\oplus g = g = g \\oplus e$.\n",
    "\n",
    "* (Existence of Inverses:) For all $g \\in \\mathbf{G}$ there exists an element $h \\in \\mathbf G$ such that $g \\oplus h = e$\n",
    "\n",
    "* (Associativity:) For all $g_1, g_2, g_3 \\in \\mathbf{G}$, $(g_1 \\oplus g_2) \\oplus g_3 = g_1 \\oplus (g_2 \\oplus g_3)$.\n",
    "\n",
    "If $\\mathbf{G}$ has finite number of elements $\\rightarrow \\mathbf{G}$ is a *finite group*\n",
    "\n",
    "$|\\mathbf{G}|$ - order of the group - number of elements in $\\mathbf{G}$\n",
    "\n",
    "$\\mathbf{G}$ is **abelian** if\n",
    "for all $g, h \\in \\mathbf{G}, g \\oplus h = h \\oplus g$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$Z_n^* = (\\{a: \\gcd(a, n) = 1\\}, \\cdot_{ \\bmod n})$. \n",
    "\n",
    "Let $n = p \\cdot q$, $\\qquad p, q$ are primes -- an abelian group of order $|Z_{pq}^*| = (p - 1)(q-1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**The factoring experiment** $\\textsf{Factor}_{\\mathcal{A}, GenModulus}(n)$\n",
    "1. $(N, p, q) := GenModulus(1^n)$\n",
    "\n",
    "2. $(p', q') = \\mathcal{A}(N)$\n",
    "\n",
    "3. Output: 1 if $p' \\cdot q' = N$ and $p', q' > 1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Definition 7.45** We say that factoring is hard relative to **GenModulus** if for all probabilistic polynomial-time algorithms $\\mathsf{A}$ there exists a negligible function **negl** such that \n",
    "$$P[\\textsf{Factor}_{\\mathcal{A}, GenModulus}(n) = 1] \\leq negl(n)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sympy import primefactors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**The factoring experiment** $\\textsf{Factor}_{\\mathcal{A}, GenModulus}(n)$\n",
    "1. $(N, p, q) := GenModulus(1^n)$\n",
    "\n",
    "2. $(p', q') = \\mathcal{A}(N)$\n",
    "\n",
    "3. Output: 1 if $p' \\cdot q' = N$ and $p', q' > 1$\n",
    "\n",
    "**Definition 7.45** We say that factoring is hard relative to **GenModulus** if for all probabilistic polynomial-time algorithms $\\mathsf{A}$ there exists a negligible function **negl** such that \n",
    "$$P[\\textsf{Factor}_{\\mathcal{A}, GenModulus}(n) = 1] \\leq negl(n)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def GenModulus(w):\n",
    "    n = len(w)\n",
    "    p = randprime(2 ** n, 2 ** (n+1))\n",
    "    q = randprime(2 ** n, 2 ** (n+1))\n",
    "    N = p * q\n",
    "    return N, p, q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def Factor(n):\n",
    "    N, p, q = GenModulus(\"1\" * n)\n",
    "    pp, qq = A(N)\n",
    "    if pp > 1 and qq > 1 and pp * qq == N:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def A(N):\n",
    "    factors = primefactors(N)\n",
    "    return factors[0], factors[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 12.4 s, sys: 0 ns, total: 12.4 s\n",
      "Wall time: 12.4 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "sec_param = 52\n",
    "num_of_succ = 0\n",
    "tries = 100\n",
    "\n",
    "for i in range(tries):\n",
    "    num_of_succ = num_of_succ + Factor(sec_param // 2)\n",
    "\n",
    "num_of_succ/tries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "488489 65537 192722\n"
     ]
    }
   ],
   "source": [
    "def GenRSA(w):\n",
    "    n = len(w)\n",
    "    N, p, q = GenModulus(w)\n",
    "    m = (p-1) * (q-1)\n",
    "    e = 2 ** 16 + 1\n",
    "    d = modinv(e, m)\n",
    "    return N, e, d, p, q\n",
    "# N, e - public key\n",
    "# N, d - private key\n",
    "\n",
    "def enc(x, N, e):\n",
    "    return x ** e % N\n",
    "\n",
    "def dec(c, N, d):\n",
    "    return c ** d % N\n",
    "\n",
    "N, e, d, p, q = GenRSA(\"111111111\")\n",
    "#print(\"private key: \", d)\n",
    "#print(\"public key: \", N, e)\n",
    "\n",
    "xx  = 120 * p % N #random.randint(2, N)\n",
    "\n",
    "y = enc(xx, N, e)\n",
    "x = dec(y, N, d)\n",
    "print(N, e, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**The RSA experiment** $\\textsf{RSA-inv}_{\\mathcal{A}, GenRSA}(n)$\n",
    "1. $(N, e, d) := GenRSA(1^n)$\n",
    "\n",
    "2. choose $y \\leftarrow Z_N^*$\n",
    "\n",
    "2. $x = \\mathcal{A}(N, e, y)$\n",
    "\n",
    "3. Output: 1 if $x^e = y \\bmod N$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Definition 7.46** We say that RSA problem is hard relative to **GenRSA** if for all probabilistic polynomial-time algorithms $\\mathsf{A}$ there exists a negligible function **negl** such that \n",
    "$$P[\\textsf{RSA-inv}_{\\mathcal{A}, GenRSA}(n) = 1] \\leq negl(n)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def randomZnElement(N):\n",
    "    g = N\n",
    "    while math.gcd(g, N) != 1:\n",
    "        g = random.randint(2, N)\n",
    "    return g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### CPA security $Pub_{\\mathcal{A}, \\Pi}^{cpa}(n):$\n",
    "\n",
    "1. $(pk, sk) \\leftarrow Gen(1^n)$\n",
    "2. * $\\mathcal{A}$ is given $pk$ and oracle access to $Enc_{pk}(\\cdot)$\n",
    "    * outputs $m_0, m_1 \\leftarrow \\mathcal{A}(pk)$, $|m_0|=|m_1|$\n",
    "3. \n",
    "    * $b \\leftarrow \\{0, 1\\}$\n",
    "    * $c \\leftarrow Enc_{pk}(m_b)$\n",
    "4. * $\\mathcal{A}$ continues to have access to $Enc_{pk}(\\cdot)$ and \n",
    "    * outputs $b' \\leftarrow \\mathcal{A}(c)$\n",
    "5. output is 1 if $b' = b$, 0 otherwise"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Definition 10.4** A public-key encryption scheme $\\Pi = (Gen, Enc, Dec)$ has **indistinguishable encryptions under a chosen-plaintext attack** (CPA-secure) if for all probabilistic polynomial-time adversaries $\\mathcal{A}$ there exists a negligible function **negl** such that:\n",
    "$$P\\left[Pub_{\\mathcal{A}, \\Pi}^{cpa}(n) = 1\\right] \\leq \\frac{1}{2} + \\textsf{negl}(n)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Is \"textbook RSA\" CPA-secure?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "it is deterministic so..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "cell_style": "center"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pub 488489 65537\n",
      "messages 378980 41295\n",
      "encryptions 46995 28202\n",
      "challenge encryption 46995\n"
     ]
    }
   ],
   "source": [
    "print(\"pub\",N, e)\n",
    "m0 = randomZnElement(N)\n",
    "m1 = randomZnElement(N)\n",
    "print(\"messages\",m0, m1)\n",
    "c0 = enc(N, e, m0)\n",
    "c1 = enc(N, e, m1)\n",
    "print(\"encryptions\", c0, c1)\n",
    "b = random.randint(0,1)\n",
    "if b == 0:\n",
    "    c = enc(N, e, m0)\n",
    "else: \n",
    "    c = enc(N, e, m1)\n",
    "print(\"challenge encryption\",c)    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Hybrid encryption\n",
    "\n",
    "**Construction 10.12** \n",
    "* $\\Pi = (Gen, Enc, Dec)$ a public-key encryption scheme\n",
    "* $\\Pi' = (Gen', Enc', Dec')$ a private-key encryption scheme\n",
    "Construct a public-key encryption $\\Pi^{hy} = (Gen^{hy}, Enc^{hy}, Dec^{hy})$:\n",
    "\n",
    "* **Gen**${}^{hy}(1^n)$: $(pk, sk) \\leftarrow Gen(1^n)$\n",
    "\n",
    "* **Enc**${}^{hy}(pk, m):$\n",
    "    1. $k \\leftarrow \\{0,1\\}^n$\n",
    "    2. \n",
    "        * $c_1 \\leftarrow Enc_{pk}(k)$, \n",
    "        * $c_2 \\leftarrow Enc'_k(m)$\n",
    "    3. $(c_1, c_2)$\n",
    "\n",
    "* **Dec**${}^{hy}(sk, c_1, c_2):$\n",
    "    1. $k = Dec_{sk}(c_1)$\n",
    "    2. $m = Dec'_{k}(c_2)$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## RSA OAEP\n",
    "\n",
    "\n",
    "![oaep](img/oaep.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Signature scheme (12.1)** a signature scheme is a tuple of three probabilistic polynomial-time algorithms $(Gen, Sign, Vrfy)$ satisfying the following:\n",
    "\n",
    "\n",
    "1. $(pk, sk) \\leftarrow Gen(1^n)$\n",
    "2. $\\sigma \\leftarrow Sign_{sk}(m)$, $m \\in \\{0, 1\\}^*$ ($Sign$ is probabilistic)\n",
    "3. $$b  = Vrfy(pk, m, \\sigma)$$\n",
    "    * $b = 1$ valid \n",
    "    * $b = 0$ invalid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Signature experiment $SigForge_{\\mathcal{A}, \\Pi}(n)$:\n",
    "\n",
    "1. $(pk, sk) \\leftarrow Gen(1^n)$\n",
    "2. \n",
    "    * $\\mathcal{A}$ is given $pk$ and oracle access to $Sign_{sk}(\\cdot)$\n",
    "    * $\\mathcal{A}$ outputs $(m, \\sigma)$\n",
    "    * $Q$ - the set of messages whose signature were requested by $\\mathcal{A}$ during its execution\n",
    "3. The output of the experiment is defined to be $1$ if and only if:\n",
    "    1. $Vrfy_{pk}(m, \\sigma) = 1$\n",
    "    2. $m \\not \\in Q$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "**Definition 12.2** A signature scheme $\\Pi = (Gen, Sign, Vrfy)$ is **existentially unforgeable under an adaptive chosen-message attack** if for all probabilistic polynomial-time adversaries $\\mathcal{A}$, there exists a negligible function **negl** such that\n",
    "$$P\\left[SigForge_{\\mathcal{A}, \\Pi}(n) = 1\\right] \\leq \\textsf{negl}(n).$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Textbook RSA signature**\n",
    "\n",
    "**Gen** $(N, e, d) \\leftarrow GenRSA(1^n)$\n",
    "\n",
    "* the public key $(N, e)$\n",
    "* the private key $(N, d)$\n",
    "\n",
    "**Sign**$([N, d], m)$, $m \\in Z_N^*$:\n",
    "\n",
    "* return $\\sigma = [m^d \\bmod N]$\n",
    "\n",
    "**Vrfy**$([N, e], m, \\sigma)$, output 1 if and only if\n",
    "\n",
    "$$ m = [\\sigma^e \\bmod N]$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def GenRSA(w):\n",
    "    n = len(w)\n",
    "    N, p, q = GenModulus(w)\n",
    "    m = (p-1) * (q-1)\n",
    "    e = 2 ** 16 + 1\n",
    "    gcd, d, y = egcd(e, m)\n",
    "    if d < 0:\n",
    "        d = m + d\n",
    "    return N, e, d\n",
    "\n",
    "def sign(x, N, d):\n",
    "    return x ** d % N\n",
    "\n",
    "def vrfy(m, sigma, N, e):\n",
    "    return m == sigma ** e % N"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Example 1** A no-message attack\n",
    "\n",
    "Goal: forge a signature under a random message"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$\\mathcal{A}([N, e])$:\n",
    "1. select $\\sigma \\leftarrow Z_N^*$\n",
    "2. compute $m = \\sigma^e \\bmod N$\n",
    "3. return $(m, \\sigma)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "N, e, d = GenRSA(\"11111\")\n",
    "\n",
    "def A(N, e):\n",
    "    sigma = randomZnElement(N)\n",
    "    m = sigma ** e % N\n",
    "    return m, sigma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1166 1996\n"
     ]
    }
   ],
   "source": [
    "m, sigma = A(N, e)\n",
    "print(m, sigma)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vrfy(m, sigma, N, e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Signature experiment $SigForge_{\\mathcal{A}, \\Pi}(n)$:\n",
    "\n",
    "1. $(pk, sk) \\leftarrow Gen(1^n)$\n",
    "2. \n",
    "    * $\\mathcal{A}$ is given $pk$ and oracle access to $Sign_{sk}(\\cdot)$\n",
    "    * $\\mathcal{A}$ outputs $(m, \\sigma)$\n",
    "    * $Q$ - the set of messages whose signature were requested by $\\mathcal{A}$ during its execution\n",
    "3. The output of the experiment is defined to be $1$ if and only if:\n",
    "    1. $Vrfy_{pk}(m, \\sigma) = 1$\n",
    "    2. $m \\not \\in Q$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Textbook RSA signature\n",
    "\n",
    "**Gen** $(N, e, d) \\leftarrow GenRSA(1^n)$\n",
    "\n",
    "* the public key $(N, e)$\n",
    "* the private key $(N, d)$\n",
    "\n",
    "**Sign**$([N, d], m)$, $m \\in Z_N^*$:\n",
    "\n",
    "* return $\\sigma = [m^d \\bmod N]$\n",
    "\n",
    "**Vrfy**$([N, e], m, \\sigma)$, output 1 if and only if\n",
    "\n",
    "$$ m = [\\sigma^e \\bmod N]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Example 2** Forging a signature on an arbitrary message"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "![forge](img/forge.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1250 1946 1520\n",
      "819 469\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = randomZnElement(N)\n",
    "m1 = randomZnElement(N)\n",
    "m2 = m * modinv(m1, N) % N\n",
    "\n",
    "s1 = sign(m1, N, d)\n",
    "s2 = sign(m2, N, d)\n",
    "\n",
    "print(m, m1, m2)\n",
    "\n",
    "print(s1, s2)\n",
    "\n",
    "\n",
    "vrfy(m, (s1 * s2) % N, N, e)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Factoring - Fermat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8353 6959 58128527\n"
     ]
    }
   ],
   "source": [
    "p = randprime(2000, 10000)\n",
    "q = randprime(2000, 10000)\n",
    "\n",
    "n = p * q\n",
    "\n",
    "print(p, q, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1 1\n",
      "2 1 1\n",
      "3 1 1\n",
      "4 1 1\n",
      "5 1 1\n",
      "6 1 1\n",
      "7 1 1\n",
      "8 1 1\n",
      "9 1 1\n",
      "10 1 1\n",
      "11 1 1\n",
      "12 1 1\n",
      "13 1 1\n",
      "14 1 1\n",
      "15 1 1\n",
      "16 1 1\n",
      "17 1 1\n",
      "18 1 1\n",
      "19 1 1\n",
      "20 1 1\n",
      "21 1 1\n",
      "22 1 1\n",
      "23 1 1\n",
      "24 1 1\n",
      "25 1 1\n",
      "26 1 1\n",
      "27 1 1\n",
      "28 1 1\n",
      "29 1 1\n",
      "30 1 1\n",
      "31 1 1\n",
      "32 1 1\n",
      "33 1 1\n",
      "34 1 1\n",
      "35 1 1\n",
      "36 1 1\n",
      "37 1 1\n",
      "38 1 1\n",
      "39 1 1\n",
      "40 1 1\n",
      "41 1 1\n",
      "42 1 1\n",
      "43 1 1\n",
      "44 1 1\n",
      "45 1 1\n",
      "46 1 1\n",
      "47 1 1\n",
      "48 1 1\n",
      "49 1 1\n",
      "50 1 1\n",
      "51 1 1\n",
      "52 1 1\n",
      "53 1 1\n",
      "54 1 1\n",
      "55 1 1\n",
      "56 1 1\n",
      "57 1 1\n",
      "58 1 1\n",
      "59 1 1\n",
      "60 1 1\n",
      "61 1 1\n",
      "62 1 1\n",
      "63 1 1\n",
      "64 1 1\n",
      "65 1 1\n",
      "66 1 1\n",
      "67 1 1\n",
      "68 1 1\n",
      "69 1 1\n",
      "70 1 1\n",
      "71 1 1\n",
      "72 1 1\n",
      "73 1 1\n",
      "74 1 1\n",
      "75 1 1\n",
      "76 1 1\n",
      "77 1 1\n",
      "78 1 1\n",
      "79 1 1\n",
      "80 1 1\n",
      "81 1 1\n",
      "82 1 1\n",
      "83 1 1\n",
      "84 1 1\n",
      "85 1 1\n",
      "86 1 1\n",
      "87 1 1\n",
      "88 1 1\n",
      "89 1 1\n",
      "90 1 1\n",
      "91 1 1\n",
      "92 1 1\n",
      "93 1 1\n",
      "94 1 1\n",
      "95 1 1\n",
      "96 1 1\n",
      "97 1 1\n",
      "98 1 1\n",
      "99 1 1\n",
      "100 1 1\n",
      "101 1 1\n",
      "102 1 1\n",
      "103 1 1\n",
      "104 1 1\n",
      "105 1 1\n",
      "106 1 1\n",
      "107 1 1\n",
      "108 1 1\n",
      "109 1 1\n",
      "110 1 1\n",
      "111 1 1\n",
      "112 1 1\n",
      "113 1 1\n",
      "114 1 1\n",
      "115 1 1\n",
      "116 1 1\n",
      "117 1 1\n",
      "118 1 1\n",
      "119 1 1\n",
      "120 1 1\n",
      "121 1 1\n",
      "122 1 1\n",
      "123 1 1\n",
      "124 1 1\n",
      "125 1 1\n",
      "126 1 1\n",
      "127 1 1\n",
      "128 1 1\n",
      "129 1 1\n",
      "130 1 1\n",
      "131 1 1\n",
      "132 1 1\n",
      "133 1 1\n",
      "134 1 1\n",
      "135 1 1\n",
      "136 1 1\n",
      "137 1 1\n",
      "138 1 1\n",
      "139 1 1\n",
      "140 1 1\n",
      "141 1 1\n",
      "142 1 1\n",
      "143 1 1\n",
      "144 1 1\n",
      "145 1 1\n",
      "146 1 1\n",
      "147 1 1\n",
      "148 1 1\n",
      "149 1 1\n",
      "150 1 1\n",
      "151 1 1\n",
      "152 1 1\n",
      "153 1 1\n",
      "154 1 1\n",
      "155 1 1\n",
      "156 1 1\n",
      "157 1 1\n",
      "158 1 1\n",
      "159 1 1\n",
      "160 1 1\n",
      "161 1 1\n",
      "162 1 1\n",
      "163 1 1\n",
      "164 1 1\n",
      "165 1 1\n",
      "166 1 1\n",
      "167 1 1\n",
      "168 1 1\n",
      "169 1 1\n",
      "170 1 1\n",
      "171 1 1\n",
      "172 1 1\n",
      "173 1 1\n",
      "174 1 1\n",
      "175 1 1\n",
      "176 1 1\n",
      "177 1 1\n",
      "178 1 1\n",
      "179 1 1\n",
      "180 1 1\n",
      "181 1 1\n",
      "182 1 1\n",
      "183 1 1\n",
      "184 1 1\n",
      "185 1 1\n",
      "186 1 1\n",
      "187 1 1\n",
      "188 1 1\n",
      "189 1 1\n",
      "190 1 1\n",
      "191 1 1\n",
      "192 1 1\n",
      "193 1 1\n",
      "194 1 1\n",
      "195 1 1\n",
      "196 1 1\n",
      "197 1 1\n",
      "198 1 1\n",
      "199 1 1\n",
      "200 1 1\n",
      "201 1 1\n",
      "202 1 1\n",
      "203 1 1\n",
      "204 1 1\n",
      "205 1 1\n",
      "206 1 1\n",
      "207 1 1\n",
      "208 1 1\n",
      "209 1 1\n",
      "210 1 1\n",
      "211 1 1\n",
      "212 1 1\n",
      "213 1 1\n",
      "214 1 1\n",
      "215 1 1\n",
      "216 1 1\n",
      "217 1 1\n",
      "218 1 1\n",
      "219 1 1\n",
      "220 1 1\n",
      "221 1 1\n",
      "222 1 1\n",
      "223 1 1\n",
      "224 1 1\n",
      "225 1 1\n",
      "226 1 1\n",
      "227 1 1\n",
      "228 1 1\n",
      "229 1 1\n",
      "230 1 1\n",
      "231 1 1\n",
      "232 1 1\n",
      "233 1 1\n",
      "234 1 1\n",
      "235 1 1\n",
      "236 1 1\n",
      "237 1 1\n",
      "238 1 1\n",
      "239 1 1\n",
      "240 1 1\n",
      "241 1 1\n",
      "242 1 1\n",
      "243 1 1\n",
      "244 1 1\n",
      "245 1 1\n",
      "246 1 1\n",
      "247 1 1\n",
      "248 1 1\n",
      "249 1 1\n",
      "250 1 1\n",
      "251 1 1\n",
      "252 1 1\n",
      "253 1 1\n",
      "254 1 1\n",
      "255 1 1\n",
      "256 1 1\n",
      "257 1 1\n",
      "258 1 1\n",
      "259 1 1\n",
      "260 1 1\n",
      "261 1 1\n",
      "262 1 1\n",
      "263 1 1\n",
      "264 1 1\n",
      "265 1 1\n",
      "266 1 1\n",
      "267 1 1\n",
      "268 1 1\n",
      "269 1 1\n",
      "270 1 1\n",
      "271 1 1\n",
      "272 1 1\n",
      "273 1 1\n",
      "274 1 1\n",
      "275 1 1\n",
      "276 1 1\n",
      "277 1 1\n",
      "278 1 1\n",
      "279 1 1\n",
      "280 1 1\n",
      "281 1 1\n",
      "282 1 1\n",
      "283 1 1\n",
      "284 1 1\n",
      "285 1 1\n",
      "286 1 1\n",
      "287 1 1\n",
      "288 1 1\n",
      "289 1 1\n",
      "290 1 1\n",
      "291 1 1\n",
      "292 1 1\n",
      "293 1 1\n",
      "294 1 1\n",
      "295 1 1\n",
      "296 1 1\n",
      "297 1 1\n",
      "298 1 1\n",
      "299 1 1\n",
      "300 1 1\n",
      "301 1 1\n",
      "302 1 1\n",
      "303 1 1\n",
      "304 1 1\n",
      "305 1 1\n",
      "306 1 1\n",
      "307 1 1\n",
      "308 1 1\n",
      "309 1 1\n",
      "310 1 1\n",
      "311 1 1\n",
      "312 1 1\n",
      "313 1 1\n",
      "314 1 1\n",
      "315 1 1\n",
      "316 1 1\n",
      "317 1 1\n",
      "318 1 1\n",
      "319 1 1\n",
      "320 1 1\n",
      "321 1 1\n",
      "322 1 1\n",
      "323 1 1\n",
      "324 1 1\n",
      "325 1 1\n",
      "326 1 1\n",
      "327 1 1\n",
      "328 1 1\n",
      "329 1 1\n",
      "330 1 1\n",
      "331 1 1\n",
      "332 1 1\n",
      "333 1 1\n",
      "334 1 1\n",
      "335 1 1\n",
      "336 1 1\n",
      "337 1 1\n",
      "338 1 1\n",
      "339 1 1\n",
      "340 1 1\n",
      "341 1 1\n",
      "342 1 1\n",
      "343 1 1\n",
      "344 1 1\n",
      "345 1 1\n",
      "346 1 1\n",
      "347 1 1\n",
      "348 1 1\n",
      "349 1 1\n",
      "350 1 1\n",
      "351 1 1\n",
      "352 1 1\n",
      "353 1 1\n",
      "354 1 1\n",
      "355 1 1\n",
      "356 1 1\n",
      "357 1 1\n",
      "358 1 1\n",
      "359 1 1\n",
      "360 1 1\n",
      "361 1 1\n",
      "362 1 1\n",
      "363 1 1\n",
      "364 1 1\n",
      "365 1 1\n",
      "366 1 1\n",
      "367 1 1\n",
      "368 1 1\n",
      "369 1 1\n",
      "370 1 1\n",
      "371 1 1\n",
      "372 1 1\n",
      "373 1 1\n",
      "374 1 1\n",
      "375 1 1\n",
      "376 1 1\n",
      "377 1 1\n",
      "378 1 1\n",
      "379 1 1\n",
      "380 1 1\n",
      "381 1 1\n",
      "382 1 1\n",
      "383 1 1\n",
      "384 1 1\n",
      "385 1 1\n",
      "386 1 1\n",
      "387 1 1\n",
      "388 1 1\n",
      "389 1 1\n",
      "390 1 1\n",
      "391 1 1\n",
      "392 1 1\n",
      "393 1 1\n",
      "394 1 1\n",
      "395 1 1\n",
      "396 1 1\n",
      "397 1 1\n",
      "398 1 1\n",
      "399 1 1\n",
      "400 1 1\n",
      "401 1 1\n",
      "402 1 1\n",
      "403 1 1\n",
      "404 1 1\n",
      "405 1 1\n",
      "406 1 1\n",
      "407 1 1\n",
      "408 1 1\n",
      "409 1 1\n",
      "410 1 1\n",
      "411 1 1\n",
      "412 1 1\n",
      "413 1 1\n",
      "414 1 1\n",
      "415 1 1\n",
      "416 1 1\n",
      "417 1 1\n",
      "418 1 1\n",
      "419 1 1\n",
      "420 1 1\n",
      "421 1 1\n",
      "422 1 1\n",
      "423 1 1\n",
      "424 1 1\n",
      "425 1 1\n",
      "426 1 1\n",
      "427 1 1\n",
      "428 1 1\n",
      "429 1 1\n",
      "430 1 1\n",
      "431 1 1\n",
      "432 1 1\n",
      "433 1 1\n",
      "434 1 1\n",
      "435 1 1\n",
      "436 1 1\n",
      "437 1 1\n",
      "438 1 1\n",
      "439 1 1\n",
      "440 1 1\n",
      "441 1 1\n",
      "442 1 1\n",
      "443 1 1\n",
      "444 1 1\n",
      "445 1 1\n",
      "446 1 1\n",
      "447 1 1\n",
      "448 1 1\n",
      "449 1 1\n",
      "450 1 1\n",
      "451 1 1\n",
      "452 1 1\n",
      "453 1 1\n",
      "454 1 1\n",
      "455 1 1\n",
      "456 1 1\n",
      "457 1 1\n",
      "458 1 1\n",
      "459 1 1\n",
      "460 1 1\n",
      "461 1 1\n",
      "462 1 1\n",
      "463 1 1\n",
      "464 1 1\n",
      "465 1 1\n",
      "466 1 1\n",
      "467 1 1\n",
      "468 1 1\n",
      "469 1 1\n",
      "470 1 1\n",
      "471 1 1\n",
      "472 1 1\n",
      "473 1 1\n",
      "474 1 1\n",
      "475 1 1\n",
      "476 1 1\n",
      "477 1 1\n",
      "478 1 1\n",
      "479 1 1\n",
      "480 1 1\n",
      "481 1 1\n",
      "482 1 1\n",
      "483 1 1\n",
      "484 1 1\n",
      "485 1 1\n",
      "486 1 1\n",
      "487 1 1\n",
      "488 1 1\n",
      "489 1 1\n",
      "490 1 1\n",
      "491 1 1\n",
      "492 1 1\n",
      "493 1 1\n",
      "494 1 1\n",
      "495 1 1\n",
      "496 1 1\n",
      "497 1 1\n",
      "498 1 1\n",
      "499 1 1\n",
      "500 1 1\n",
      "501 1 1\n",
      "502 1 1\n",
      "503 1 1\n",
      "504 1 1\n",
      "505 1 1\n",
      "506 1 1\n",
      "507 1 1\n",
      "508 1 1\n",
      "509 1 1\n",
      "510 1 1\n",
      "511 1 1\n",
      "512 1 1\n",
      "513 1 1\n",
      "514 1 1\n",
      "515 1 1\n",
      "516 1 1\n",
      "517 1 1\n",
      "518 1 1\n",
      "519 1 1\n",
      "520 1 1\n",
      "521 1 1\n",
      "522 1 1\n",
      "523 1 1\n",
      "524 1 1\n",
      "525 1 1\n",
      "526 1 1\n",
      "527 1 1\n",
      "528 1 1\n",
      "529 1 1\n",
      "530 1 1\n",
      "531 1 1\n",
      "532 1 1\n",
      "533 1 1\n",
      "534 1 1\n",
      "535 1 1\n",
      "536 1 1\n",
      "537 1 1\n",
      "538 1 1\n",
      "539 1 1\n",
      "540 1 1\n",
      "541 1 1\n",
      "542 1 1\n",
      "543 1 1\n",
      "544 1 1\n",
      "545 1 1\n",
      "546 1 1\n",
      "547 1 1\n",
      "548 1 1\n",
      "549 1 1\n",
      "550 1 1\n",
      "551 1 1\n",
      "552 1 1\n",
      "553 1 1\n",
      "554 1 1\n",
      "555 1 1\n",
      "556 1 1\n",
      "557 1 1\n",
      "558 1 1\n",
      "559 1 1\n",
      "560 1 1\n",
      "561 1 1\n",
      "562 1 1\n",
      "563 1 1\n",
      "564 1 1\n",
      "565 1 1\n",
      "566 1 1\n",
      "567 1 1\n",
      "568 1 1\n",
      "569 1 1\n",
      "570 1 1\n",
      "571 1 1\n",
      "572 1 1\n",
      "573 1 1\n",
      "574 1 1\n",
      "575 1 1\n",
      "576 1 1\n",
      "577 1 1\n",
      "578 1 1\n",
      "579 1 1\n",
      "580 1 1\n",
      "581 1 1\n",
      "582 1 1\n",
      "583 1 1\n",
      "584 1 1\n",
      "585 1 1\n",
      "586 1 1\n",
      "587 1 1\n",
      "588 1 1\n",
      "589 1 1\n",
      "590 1 1\n",
      "591 1 1\n",
      "592 1 1\n",
      "593 1 1\n",
      "594 1 1\n",
      "595 1 1\n",
      "596 1 1\n",
      "597 1 1\n",
      "598 1 1\n",
      "599 1 1\n",
      "600 1 1\n",
      "601 1 1\n",
      "602 1 1\n",
      "603 1 1\n",
      "604 1 1\n",
      "605 1 1\n",
      "606 1 1\n",
      "607 1 1\n",
      "608 1 1\n",
      "609 1 1\n",
      "610 1 1\n",
      "611 1 1\n",
      "612 1 1\n",
      "613 1 1\n",
      "614 1 1\n",
      "615 1 1\n",
      "616 1 1\n",
      "617 1 1\n",
      "618 1 1\n",
      "619 1 1\n",
      "620 1 1\n",
      "621 1 1\n",
      "622 1 1\n",
      "623 1 1\n",
      "624 1 1\n",
      "625 1 1\n",
      "626 1 1\n",
      "627 1 1\n",
      "628 1 1\n",
      "629 1 1\n",
      "630 1 1\n",
      "631 1 1\n",
      "632 1 1\n",
      "633 1 1\n",
      "634 1 1\n",
      "635 1 1\n",
      "636 1 1\n",
      "637 1 1\n",
      "638 1 1\n",
      "639 1 1\n",
      "640 1 1\n",
      "641 1 1\n",
      "642 1 1\n",
      "643 1 1\n",
      "644 1 1\n",
      "645 1 1\n",
      "646 1 1\n",
      "647 1 1\n",
      "648 1 1\n",
      "649 1 1\n",
      "650 1 1\n",
      "651 1 1\n",
      "652 1 1\n",
      "653 1 1\n",
      "654 1 1\n",
      "655 1 1\n",
      "656 1 1\n",
      "657 1 1\n",
      "658 1 1\n",
      "659 1 1\n",
      "660 1 1\n",
      "661 1 1\n",
      "662 1 1\n",
      "663 1 1\n",
      "664 1 1\n",
      "665 1 1\n",
      "666 1 1\n",
      "667 1 1\n",
      "668 1 1\n",
      "669 1 1\n",
      "670 1 1\n",
      "671 1 1\n",
      "672 1 1\n",
      "673 1 1\n",
      "674 1 1\n",
      "675 1 1\n",
      "676 1 1\n",
      "677 1 1\n",
      "678 1 1\n",
      "679 1 1\n",
      "680 1 1\n",
      "681 1 1\n",
      "682 1 1\n",
      "683 1 1\n",
      "684 1 1\n",
      "685 1 1\n",
      "686 1 1\n",
      "687 1 1\n",
      "688 1 1\n",
      "689 1 1\n",
      "690 1 1\n",
      "691 1 1\n",
      "692 1 1\n",
      "693 1 1\n",
      "694 1 1\n",
      "695 1 1\n",
      "696 1 1\n",
      "697 1 1\n",
      "698 1 1\n",
      "699 1 1\n",
      "700 1 1\n",
      "701 1 1\n",
      "702 1 1\n",
      "703 1 1\n",
      "704 1 1\n",
      "705 1 1\n",
      "706 1 1\n",
      "707 1 1\n",
      "708 1 1\n",
      "709 1 1\n",
      "710 1 1\n",
      "711 1 1\n",
      "712 1 1\n",
      "713 1 1\n",
      "714 1 1\n",
      "715 1 1\n",
      "716 1 1\n",
      "717 1 1\n",
      "718 1 1\n",
      "719 1 1\n",
      "720 1 1\n",
      "721 1 1\n",
      "722 1 1\n",
      "723 1 1\n",
      "724 1 1\n",
      "725 1 1\n",
      "726 1 1\n",
      "727 1 1\n",
      "728 1 1\n",
      "729 1 1\n",
      "730 1 1\n",
      "731 1 1\n",
      "732 1 1\n",
      "733 1 1\n",
      "734 1 1\n",
      "735 1 1\n",
      "736 1 1\n",
      "737 1 1\n",
      "738 1 1\n",
      "739 1 1\n",
      "740 1 1\n",
      "741 1 1\n",
      "742 1 1\n",
      "743 1 1\n",
      "744 1 1\n",
      "745 1 1\n",
      "746 1 1\n",
      "747 1 1\n",
      "748 1 1\n",
      "749 1 1\n",
      "750 1 1\n",
      "751 1 1\n",
      "752 1 1\n",
      "753 1 1\n",
      "754 1 1\n",
      "755 1 1\n",
      "756 1 1\n",
      "757 1 1\n",
      "758 1 1\n",
      "759 1 1\n",
      "760 1 1\n",
      "761 1 1\n",
      "762 1 1\n",
      "763 1 1\n",
      "764 1 1\n",
      "765 1 1\n",
      "766 1 1\n",
      "767 1 1\n",
      "768 1 1\n",
      "769 1 1\n",
      "770 1 1\n",
      "771 1 1\n",
      "772 1 1\n",
      "773 1 1\n",
      "774 1 1\n",
      "775 1 1\n",
      "776 1 1\n",
      "777 1 1\n",
      "778 1 1\n",
      "779 1 1\n",
      "780 1 1\n",
      "781 1 1\n",
      "782 1 1\n",
      "783 1 1\n",
      "784 1 1\n",
      "785 1 1\n",
      "786 1 1\n",
      "787 1 1\n",
      "788 1 1\n",
      "789 1 1\n",
      "790 1 1\n",
      "791 1 1\n",
      "792 1 1\n",
      "793 1 1\n",
      "794 1 1\n",
      "795 1 1\n",
      "796 1 1\n",
      "797 1 1\n",
      "798 1 1\n",
      "799 1 1\n",
      "800 1 1\n",
      "801 1 1\n",
      "802 1 1\n",
      "803 1 1\n",
      "804 1 1\n",
      "805 1 1\n",
      "806 1 1\n",
      "807 1 1\n",
      "808 1 1\n",
      "809 1 1\n",
      "810 1 1\n",
      "811 1 1\n",
      "812 1 1\n",
      "813 1 1\n",
      "814 1 1\n",
      "815 1 1\n",
      "816 1 1\n",
      "817 1 1\n",
      "818 1 1\n",
      "819 1 1\n",
      "820 1 1\n",
      "821 1 1\n",
      "822 1 1\n",
      "823 1 1\n",
      "824 1 1\n",
      "825 1 1\n",
      "826 1 1\n",
      "827 1 1\n",
      "828 1 1\n",
      "829 1 1\n",
      "830 1 1\n",
      "831 1 1\n",
      "832 1 1\n",
      "833 1 1\n",
      "834 1 1\n",
      "835 1 1\n",
      "836 1 1\n",
      "837 1 1\n",
      "838 1 1\n",
      "839 1 1\n",
      "840 1 1\n",
      "841 1 1\n",
      "842 1 1\n",
      "843 1 1\n",
      "844 1 1\n",
      "845 1 1\n",
      "846 1 1\n",
      "847 1 1\n",
      "848 1 1\n",
      "849 1 1\n",
      "850 1 1\n",
      "851 1 1\n",
      "852 1 1\n",
      "853 1 1\n",
      "854 1 1\n",
      "855 1 1\n",
      "856 1 1\n",
      "857 1 1\n",
      "858 1 1\n",
      "859 1 1\n",
      "860 1 1\n",
      "861 1 1\n",
      "862 1 1\n",
      "863 1 1\n",
      "864 1 1\n",
      "865 1 1\n",
      "866 1 1\n",
      "867 1 1\n",
      "868 1 1\n",
      "869 1 1\n",
      "870 1 1\n",
      "871 1 1\n",
      "872 1 1\n",
      "873 1 1\n",
      "874 1 1\n",
      "875 1 1\n",
      "876 1 1\n",
      "877 1 1\n",
      "878 1 1\n",
      "879 1 1\n",
      "880 1 1\n",
      "881 1 1\n",
      "882 1 1\n",
      "883 1 1\n",
      "884 1 1\n",
      "885 1 1\n",
      "886 1 1\n",
      "887 1 1\n",
      "888 1 1\n",
      "889 1 1\n",
      "890 1 1\n",
      "891 1 1\n",
      "892 1 1\n",
      "893 1 1\n",
      "894 1 1\n",
      "895 1 1\n",
      "896 1 1\n",
      "897 1 1\n",
      "898 1 1\n",
      "899 1 1\n",
      "900 1 1\n",
      "901 1 1\n",
      "902 1 1\n",
      "903 1 1\n",
      "904 1 1\n",
      "905 1 1\n",
      "906 1 1\n",
      "907 1 1\n",
      "908 1 1\n",
      "909 1 1\n",
      "910 1 1\n",
      "911 1 1\n",
      "912 1 1\n",
      "913 1 1\n",
      "914 1 1\n",
      "915 1 1\n",
      "916 1 1\n",
      "917 1 1\n",
      "918 1 1\n",
      "919 1 1\n",
      "920 1 1\n",
      "921 1 1\n",
      "922 1 1\n",
      "923 1 1\n",
      "924 1 1\n",
      "925 1 1\n",
      "926 1 1\n",
      "927 1 1\n",
      "928 1 1\n",
      "929 1 1\n",
      "930 1 1\n",
      "931 1 1\n",
      "932 1 1\n",
      "933 1 1\n",
      "934 1 1\n",
      "935 1 1\n",
      "936 1 1\n",
      "937 1 1\n",
      "938 1 1\n",
      "939 1 1\n",
      "940 1 1\n",
      "941 1 1\n",
      "942 1 1\n",
      "943 1 1\n",
      "944 1 1\n",
      "945 1 1\n",
      "946 1 1\n",
      "947 1 1\n",
      "948 1 1\n",
      "949 1 1\n",
      "950 1 1\n",
      "951 1 1\n",
      "952 1 1\n",
      "953 1 1\n",
      "954 1 1\n",
      "955 1 1\n",
      "956 1 1\n",
      "957 1 1\n",
      "958 1 1\n",
      "959 1 1\n",
      "960 1 1\n",
      "961 1 1\n",
      "962 1 1\n",
      "963 1 1\n",
      "964 1 1\n",
      "965 1 1\n",
      "966 1 1\n",
      "967 1 1\n",
      "968 1 1\n",
      "969 1 1\n",
      "970 1 1\n",
      "971 1 1\n",
      "972 1 1\n",
      "973 1 1\n",
      "974 1 1\n",
      "975 1 1\n",
      "976 1 1\n",
      "977 1 1\n",
      "978 1 1\n",
      "979 1 1\n",
      "980 1 1\n",
      "981 1 1\n",
      "982 1 1\n",
      "983 1 1\n",
      "984 1 1\n",
      "985 1 1\n",
      "986 1 1\n",
      "987 1 1\n",
      "988 1 1\n",
      "989 1 1\n",
      "990 1 1\n",
      "991 1 1\n",
      "992 1 1\n",
      "993 1 1\n",
      "994 1 1\n",
      "995 1 1\n",
      "996 1 1\n",
      "997 1 1\n",
      "998 1 1\n",
      "999 1 1\n",
      "1000 1 1\n",
      "1001 1 1\n",
      "1002 1 1\n",
      "1003 1 1\n",
      "1004 1 1\n",
      "1005 1 1\n",
      "1006 1 1\n",
      "1007 1 1\n",
      "1008 1 1\n",
      "1009 1 1\n",
      "1010 1 1\n",
      "1011 1 1\n",
      "1012 1 1\n",
      "1013 1 1\n",
      "1014 1 1\n",
      "1015 1 1\n",
      "1016 1 1\n",
      "1017 1 1\n",
      "1018 1 1\n",
      "1019 1 1\n",
      "1020 1 1\n",
      "1021 1 1\n",
      "1022 1 1\n",
      "1023 1 1\n",
      "1024 1 1\n",
      "1025 1 1\n",
      "1026 1 1\n",
      "1027 1 1\n",
      "1028 1 1\n",
      "1029 1 1\n",
      "1030 1 1\n",
      "1031 1 1\n",
      "1032 1 1\n",
      "1033 1 1\n",
      "1034 1 1\n",
      "1035 1 1\n",
      "1036 1 1\n",
      "1037 1 1\n",
      "1038 1 1\n",
      "1039 1 1\n",
      "1040 1 1\n",
      "1041 1 1\n",
      "1042 1 1\n",
      "1043 1 1\n",
      "1044 1 1\n",
      "1045 1 1\n",
      "1046 1 1\n",
      "1047 1 1\n",
      "1048 1 1\n",
      "1049 1 1\n",
      "1050 1 1\n",
      "1051 1 1\n",
      "1052 1 1\n",
      "1053 1 1\n",
      "1054 1 1\n",
      "1055 1 1\n",
      "1056 1 1\n",
      "1057 1 1\n",
      "1058 1 1\n",
      "1059 1 1\n",
      "1060 1 1\n",
      "1061 1 1\n",
      "1062 1 1\n",
      "1063 1 1\n",
      "1064 1 1\n",
      "1065 1 1\n",
      "1066 1 1\n",
      "1067 1 1\n",
      "1068 1 1\n",
      "1069 1 1\n",
      "1070 1 1\n",
      "1071 1 1\n",
      "1072 1 1\n",
      "1073 1 1\n",
      "1074 1 1\n",
      "1075 1 1\n",
      "1076 1 1\n",
      "1077 1 1\n",
      "1078 1 1\n",
      "1079 1 1\n",
      "1080 1 1\n",
      "1081 1 1\n",
      "1082 1 1\n",
      "1083 1 1\n",
      "1084 1 1\n",
      "1085 1 1\n",
      "1086 1 1\n",
      "1087 1 1\n",
      "1088 1 1\n",
      "1089 1 1\n",
      "1090 1 1\n",
      "1091 1 1\n",
      "1092 1 1\n",
      "1093 1 1\n",
      "1094 1 1\n",
      "1095 1 1\n",
      "1096 1 1\n",
      "1097 1 1\n",
      "1098 1 1\n",
      "1099 1 1\n",
      "1100 1 1\n",
      "1101 1 1\n",
      "1102 1 1\n",
      "1103 1 1\n",
      "1104 1 1\n",
      "1105 1 1\n",
      "1106 1 1\n",
      "1107 1 1\n",
      "1108 1 1\n",
      "1109 1 1\n",
      "1110 1 1\n",
      "1111 1 1\n",
      "1112 1 1\n",
      "1113 1 1\n",
      "1114 1 1\n",
      "1115 1 1\n",
      "1116 1 1\n",
      "1117 1 1\n",
      "1118 1 1\n",
      "1119 1 1\n",
      "1120 1 1\n",
      "1121 1 1\n",
      "1122 1 1\n",
      "1123 1 1\n",
      "1124 1 1\n",
      "1125 1 1\n",
      "1126 1 1\n",
      "1127 1 1\n",
      "1128 1 1\n",
      "1129 1 1\n",
      "1130 1 1\n",
      "1131 1 1\n",
      "1132 1 1\n",
      "1133 1 1\n",
      "1134 1 1\n",
      "1135 1 1\n",
      "1136 1 1\n",
      "1137 1 1\n",
      "1138 1 1\n",
      "1139 1 1\n",
      "1140 1 1\n",
      "1141 1 1\n",
      "1142 1 1\n",
      "1143 1 1\n",
      "1144 1 1\n",
      "1145 1 1\n",
      "1146 1 1\n",
      "1147 1 1\n",
      "1148 1 1\n",
      "1149 1 1\n",
      "1150 1 1\n",
      "1151 1 1\n",
      "1152 1 1\n",
      "1153 1 1\n",
      "1154 1 1\n",
      "1155 1 1\n",
      "1156 1 1\n",
      "1157 1 1\n",
      "1158 1 1\n",
      "1159 1 1\n",
      "1160 1 1\n",
      "1161 1 1\n",
      "1162 1 1\n",
      "1163 1 1\n",
      "1164 1 1\n",
      "1165 1 1\n",
      "1166 1 1\n",
      "1167 1 1\n",
      "1168 1 1\n",
      "1169 1 1\n",
      "1170 1 1\n",
      "1171 1 1\n",
      "1172 1 1\n",
      "1173 1 1\n",
      "1174 1 1\n",
      "1175 1 1\n",
      "1176 1 1\n",
      "1177 1 1\n",
      "1178 1 1\n",
      "1179 1 1\n",
      "1180 1 1\n",
      "1181 1 1\n",
      "1182 1 1\n",
      "1183 1 1\n",
      "1184 1 1\n",
      "1185 1 1\n",
      "1186 1 1\n",
      "1187 1 1\n",
      "1188 1 1\n",
      "1189 1 1\n",
      "1190 1 1\n",
      "1191 1 1\n",
      "1192 1 1\n",
      "1193 1 1\n",
      "1194 1 1\n",
      "1195 1 1\n",
      "1196 1 1\n",
      "1197 1 1\n",
      "1198 1 1\n",
      "1199 1 1\n",
      "1200 1 1\n",
      "1201 1 1\n",
      "1202 1 1\n",
      "1203 1 1\n",
      "1204 1 1\n",
      "1205 1 1\n",
      "1206 1 1\n",
      "1207 1 1\n",
      "1208 1 1\n",
      "1209 1 1\n",
      "1210 1 1\n",
      "1211 1 1\n",
      "1212 1 1\n",
      "1213 1 1\n",
      "1214 1 1\n",
      "1215 1 1\n",
      "1216 1 1\n",
      "1217 1 1\n",
      "1218 1 1\n",
      "1219 1 1\n",
      "1220 1 1\n",
      "1221 1 1\n",
      "1222 1 1\n",
      "1223 1 1\n",
      "1224 1 1\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1225 1 1\n",
      "1226 1 1\n",
      "1227 1 1\n",
      "1228 1 1\n",
      "1229 1 1\n",
      "1230 1 1\n",
      "1231 1 1\n",
      "1232 1 1\n",
      "1233 1 1\n",
      "1234 1 1\n",
      "1235 1 1\n",
      "1236 1 1\n",
      "1237 1 1\n",
      "1238 1 1\n",
      "1239 1 1\n",
      "1240 1 1\n",
      "1241 1 1\n",
      "1242 1 1\n",
      "1243 1 1\n",
      "1244 1 1\n",
      "1245 1 1\n",
      "1246 1 1\n",
      "1247 1 1\n",
      "1248 1 1\n",
      "1249 1 1\n",
      "1250 1 1\n",
      "1251 1 1\n",
      "1252 1 1\n",
      "1253 1 1\n",
      "1254 1 1\n",
      "1255 1 1\n",
      "1256 1 1\n",
      "1257 1 1\n",
      "1258 1 1\n",
      "1259 1 1\n",
      "1260 1 1\n",
      "1261 1 1\n",
      "1262 1 1\n",
      "1263 1 1\n",
      "1264 1 1\n",
      "1265 1 1\n",
      "1266 1 1\n",
      "1267 1 1\n",
      "1268 1 1\n",
      "1269 1 1\n",
      "1270 1 1\n",
      "1271 1 1\n",
      "1272 1 1\n",
      "1273 1 1\n",
      "1274 1 1\n",
      "1275 1 1\n",
      "1276 1 1\n",
      "1277 1 1\n",
      "1278 1 1\n",
      "1279 1 1\n",
      "1280 1 1\n",
      "1281 1 1\n",
      "1282 1 1\n",
      "1283 1 1\n",
      "1284 1 1\n",
      "1285 1 1\n",
      "1286 1 1\n",
      "1287 1 1\n",
      "1288 1 1\n",
      "1289 1 1\n",
      "1290 1 1\n",
      "1291 1 1\n",
      "1292 1 1\n",
      "1293 1 1\n",
      "1294 1 1\n",
      "1295 1 1\n",
      "1296 1 1\n",
      "1297 1 1\n",
      "1298 1 1\n",
      "1299 1 1\n",
      "1300 1 1\n",
      "1301 1 1\n",
      "1302 1 1\n",
      "1303 1 1\n",
      "1304 1 1\n",
      "1305 1 1\n",
      "1306 1 1\n",
      "1307 1 1\n",
      "1308 1 1\n",
      "1309 1 1\n",
      "1310 1 1\n",
      "1311 1 1\n",
      "1312 1 1\n",
      "1313 1 1\n",
      "1314 1 1\n",
      "1315 1 1\n",
      "1316 1 1\n",
      "1317 1 1\n",
      "1318 1 1\n",
      "1319 1 1\n",
      "1320 1 1\n",
      "1321 1 1\n",
      "1322 1 1\n",
      "1323 1 1\n",
      "1324 1 1\n",
      "1325 1 1\n",
      "1326 1 1\n",
      "1327 1 1\n",
      "1328 1 1\n",
      "1329 1 1\n",
      "1330 1 1\n",
      "1331 1 1\n",
      "1332 1 1\n",
      "1333 1 1\n",
      "1334 1 1\n",
      "1335 1 1\n",
      "1336 1 1\n",
      "1337 1 1\n",
      "1338 1 1\n",
      "1339 1 1\n",
      "1340 1 1\n",
      "1341 1 1\n",
      "1342 1 1\n",
      "1343 1 1\n",
      "1344 1 1\n",
      "1345 1 1\n",
      "1346 1 1\n",
      "1347 1 1\n",
      "1348 1 1\n",
      "1349 1 1\n",
      "1350 1 1\n",
      "1351 1 1\n",
      "1352 1 1\n",
      "1353 1 1\n",
      "1354 1 1\n",
      "1355 1 1\n",
      "1356 1 1\n",
      "1357 1 1\n",
      "1358 1 1\n",
      "1359 1 1\n",
      "1360 1 1\n",
      "1361 1 1\n",
      "1362 1 1\n",
      "1363 1 1\n",
      "1364 1 1\n",
      "1365 1 1\n",
      "1366 1 1\n",
      "1367 1 1\n",
      "1368 1 1\n",
      "1369 1 1\n",
      "1370 1 1\n",
      "1371 1 1\n",
      "1372 1 1\n",
      "1373 1 1\n",
      "1374 1 1\n",
      "1375 1 1\n",
      "1376 1 1\n",
      "1377 1 1\n",
      "1378 1 1\n",
      "1379 1 1\n",
      "1380 1 1\n",
      "1381 1 1\n",
      "1382 1 1\n",
      "1383 1 1\n",
      "1384 1 1\n",
      "1385 1 1\n",
      "1386 1 1\n",
      "1387 1 1\n",
      "1388 1 1\n",
      "1389 1 1\n",
      "1390 1 1\n",
      "1391 1 1\n",
      "1392 1 1\n",
      "1393 1 1\n",
      "1394 1 1\n",
      "1395 1 1\n",
      "1396 1 1\n",
      "1397 1 1\n",
      "1398 1 1\n",
      "1399 1 1\n",
      "1400 1 1\n",
      "1401 1 1\n",
      "1402 1 1\n",
      "1403 1 1\n",
      "1404 1 1\n",
      "1405 1 1\n",
      "1406 1 1\n",
      "1407 1 1\n",
      "1408 1 1\n",
      "1409 1 1\n",
      "1410 1 1\n",
      "1411 1 1\n",
      "1412 1 1\n",
      "1413 1 1\n",
      "1414 1 1\n",
      "1415 1 1\n",
      "1416 1 1\n",
      "1417 1 1\n",
      "1418 1 1\n",
      "1419 1 1\n",
      "1420 1 1\n",
      "1421 1 1\n",
      "1422 1 1\n",
      "1423 1 1\n",
      "1424 1 1\n",
      "1425 1 1\n",
      "1426 1 1\n",
      "1427 1 1\n",
      "1428 1 1\n",
      "1429 1 1\n",
      "1430 1 1\n",
      "1431 1 1\n",
      "1432 1 1\n",
      "1433 1 1\n",
      "1434 1 1\n",
      "1435 1 1\n",
      "1436 1 1\n",
      "1437 1 1\n",
      "1438 1 1\n",
      "1439 1 1\n",
      "1440 1 1\n",
      "1441 1 1\n",
      "1442 1 1\n",
      "1443 1 1\n",
      "1444 1 1\n",
      "1445 1 1\n",
      "1446 1 1\n",
      "1447 1 1\n",
      "1448 1 1\n",
      "1449 1 1\n",
      "1450 1 1\n",
      "1451 1 1\n",
      "1452 1 1\n",
      "1453 1 1\n",
      "1454 1 1\n",
      "1455 1 1\n",
      "1456 1 1\n",
      "1457 1 1\n",
      "1458 1 1\n",
      "1459 1 1\n",
      "1460 1 1\n",
      "1461 1 1\n",
      "1462 1 1\n",
      "1463 1 1\n",
      "1464 1 1\n",
      "1465 1 1\n",
      "1466 1 1\n",
      "1467 1 1\n",
      "1468 1 1\n",
      "1469 1 1\n",
      "1470 1 1\n",
      "1471 1 1\n",
      "1472 1 1\n",
      "1473 1 1\n",
      "1474 1 1\n",
      "1475 1 1\n",
      "1476 1 1\n",
      "1477 1 1\n",
      "1478 1 1\n",
      "1479 1 1\n",
      "1480 1 1\n",
      "1481 1 1\n",
      "1482 1 1\n",
      "1483 1 1\n",
      "1484 1 1\n",
      "1485 1 1\n",
      "1486 1 1\n",
      "1487 1 1\n",
      "1488 1 1\n",
      "1489 1 1\n",
      "1490 1 1\n",
      "1491 1 1\n",
      "1492 1 1\n",
      "1493 1 1\n",
      "1494 1 1\n",
      "1495 1 1\n",
      "1496 1 1\n",
      "1497 1 1\n",
      "1498 1 1\n",
      "1499 1 1\n",
      "1500 1 1\n",
      "1501 1 1\n",
      "1502 1 1\n",
      "1503 1 1\n",
      "1504 1 1\n",
      "1505 1 1\n",
      "1506 1 1\n",
      "1507 1 1\n",
      "1508 1 1\n",
      "1509 1 1\n",
      "1510 1 1\n",
      "1511 1 1\n",
      "1512 1 1\n",
      "1513 1 1\n",
      "1514 1 1\n",
      "1515 1 1\n",
      "1516 1 1\n",
      "1517 1 1\n",
      "1518 1 1\n",
      "1519 1 1\n",
      "1520 1 1\n",
      "1521 1 1\n",
      "1522 1 1\n",
      "1523 1 1\n",
      "1524 1 1\n",
      "1525 1 1\n",
      "1526 1 1\n",
      "1527 1 1\n",
      "1528 1 1\n",
      "1529 1 1\n",
      "1530 1 1\n",
      "1531 1 1\n",
      "1532 1 1\n",
      "1533 1 1\n",
      "1534 1 1\n",
      "1535 1 1\n",
      "1536 1 1\n",
      "1537 1 1\n",
      "1538 1 1\n",
      "1539 1 1\n",
      "1540 1 1\n",
      "1541 1 1\n",
      "1542 1 1\n",
      "1543 1 1\n",
      "1544 1 1\n",
      "1545 1 1\n",
      "1546 1 1\n",
      "1547 1 1\n",
      "1548 1 1\n",
      "1549 1 1\n",
      "1550 1 1\n",
      "1551 1 1\n",
      "1552 1 1\n",
      "1553 1 1\n",
      "1554 1 1\n",
      "1555 1 1\n",
      "1556 1 1\n",
      "1557 1 1\n",
      "1558 1 1\n",
      "1559 1 1\n",
      "1560 1 1\n",
      "1561 1 1\n",
      "1562 1 1\n",
      "1563 1 1\n",
      "1564 1 1\n",
      "1565 1 1\n",
      "1566 1 1\n",
      "1567 1 1\n",
      "1568 1 1\n",
      "1569 1 1\n",
      "1570 1 1\n",
      "1571 1 1\n",
      "1572 1 1\n",
      "1573 1 1\n",
      "1574 1 1\n",
      "1575 1 1\n",
      "1576 1 1\n",
      "1577 1 1\n",
      "1578 1 1\n",
      "1579 1 1\n",
      "1580 1 1\n",
      "1581 1 1\n",
      "1582 1 1\n",
      "1583 1 1\n",
      "1584 1 1\n",
      "1585 1 1\n",
      "1586 1 1\n",
      "1587 1 1\n",
      "1588 1 1\n",
      "1589 1 1\n",
      "1590 1 1\n",
      "1591 1 1\n",
      "1592 1 1\n",
      "1593 1 1\n",
      "1594 1 1\n",
      "1595 1 1\n",
      "1596 1 1\n",
      "1597 1 1\n",
      "1598 1 1\n",
      "1599 1 1\n",
      "1600 1 1\n",
      "1601 1 1\n",
      "1602 1 1\n",
      "1603 1 1\n",
      "1604 1 1\n",
      "1605 1 1\n",
      "1606 1 1\n",
      "1607 1 1\n",
      "1608 1 1\n",
      "1609 1 1\n",
      "1610 1 1\n",
      "1611 1 1\n",
      "1612 1 1\n",
      "1613 1 1\n",
      "1614 1 1\n",
      "1615 1 1\n",
      "1616 1 1\n",
      "1617 1 1\n",
      "1618 1 1\n",
      "1619 1 1\n",
      "1620 1 1\n",
      "1621 1 1\n",
      "1622 1 1\n",
      "1623 1 1\n",
      "1624 1 1\n",
      "1625 1 1\n",
      "1626 1 1\n",
      "1627 1 1\n",
      "1628 1 1\n",
      "1629 1 1\n",
      "1630 1 1\n",
      "1631 1 1\n",
      "1632 1 1\n",
      "1633 1 1\n",
      "1634 1 1\n",
      "1635 1 1\n",
      "1636 1 1\n",
      "1637 1 1\n",
      "1638 1 1\n",
      "1639 1 1\n",
      "1640 1 1\n",
      "1641 1 1\n",
      "1642 1 1\n",
      "1643 1 1\n",
      "1644 1 1\n",
      "1645 1 1\n",
      "1646 1 1\n",
      "1647 1 1\n",
      "1648 1 1\n",
      "1649 1 1\n",
      "1650 1 1\n",
      "1651 1 1\n",
      "1652 1 1\n",
      "1653 1 1\n",
      "1654 1 1\n",
      "1655 1 1\n",
      "1656 1 1\n",
      "1657 1 1\n",
      "1658 1 1\n",
      "1659 1 1\n",
      "1660 1 1\n",
      "1661 1 1\n",
      "1662 1 1\n",
      "1663 1 1\n",
      "1664 1 1\n",
      "1665 1 1\n",
      "1666 1 1\n",
      "1667 1 1\n",
      "1668 1 1\n",
      "1669 1 1\n",
      "1670 1 1\n",
      "1671 1 1\n",
      "1672 1 1\n",
      "1673 1 1\n",
      "1674 1 1\n",
      "1675 1 1\n",
      "1676 1 1\n",
      "1677 1 1\n",
      "1678 1 1\n",
      "1679 1 1\n",
      "1680 1 1\n",
      "1681 1 1\n",
      "1682 1 1\n",
      "1683 1 1\n",
      "1684 1 1\n",
      "1685 1 1\n",
      "1686 1 1\n",
      "1687 1 1\n",
      "1688 1 1\n",
      "1689 1 1\n",
      "1690 1 1\n",
      "1691 1 1\n",
      "1692 1 1\n",
      "1693 1 1\n",
      "1694 1 1\n",
      "1695 1 1\n",
      "1696 1 1\n",
      "1697 1 1\n",
      "1698 1 1\n",
      "1699 1 1\n",
      "1700 1 1\n",
      "1701 1 1\n",
      "1702 1 1\n",
      "1703 1 1\n",
      "1704 1 1\n",
      "1705 1 1\n",
      "1706 1 1\n",
      "1707 1 1\n",
      "1708 1 1\n",
      "1709 1 1\n",
      "1710 1 1\n",
      "1711 1 1\n",
      "1712 1 1\n",
      "1713 1 1\n",
      "1714 1 1\n",
      "1715 1 1\n",
      "1716 1 1\n",
      "1717 1 1\n",
      "1718 1 1\n",
      "1719 1 1\n",
      "1720 1 1\n",
      "1721 1 1\n",
      "1722 1 1\n",
      "1723 1 1\n",
      "1724 1 1\n",
      "1725 1 1\n",
      "1726 1 1\n",
      "1727 1 1\n",
      "1728 1 1\n",
      "1729 1 1\n",
      "1730 1 1\n",
      "1731 1 1\n",
      "1732 1 1\n",
      "1733 1 1\n",
      "1734 1 1\n",
      "1735 1 1\n",
      "1736 1 1\n",
      "1737 1 1\n",
      "1738 1 1\n",
      "1739 1 1\n",
      "1740 1 1\n",
      "1741 1 1\n",
      "1742 1 1\n",
      "1743 1 1\n",
      "1744 1 1\n",
      "1745 1 1\n",
      "1746 1 1\n",
      "1747 1 1\n",
      "1748 1 1\n",
      "1749 1 1\n",
      "1750 1 1\n",
      "1751 1 1\n",
      "1752 1 1\n",
      "1753 1 1\n",
      "1754 1 1\n",
      "1755 1 1\n",
      "1756 1 1\n",
      "1757 1 1\n",
      "1758 1 1\n",
      "1759 1 1\n",
      "1760 1 1\n",
      "1761 1 1\n",
      "1762 1 1\n",
      "1763 1 1\n",
      "1764 1 1\n",
      "1765 1 1\n",
      "1766 1 1\n",
      "1767 1 1\n",
      "1768 1 1\n",
      "1769 1 1\n",
      "1770 1 1\n",
      "1771 1 1\n",
      "1772 1 1\n",
      "1773 1 1\n",
      "1774 1 1\n",
      "1775 1 1\n",
      "1776 1 1\n",
      "1777 1 1\n",
      "1778 1 1\n",
      "1779 1 1\n",
      "1780 1 1\n",
      "1781 1 1\n",
      "1782 1 1\n",
      "1783 1 1\n",
      "1784 1 1\n",
      "1785 1 1\n",
      "1786 1 1\n",
      "1787 1 1\n",
      "1788 1 1\n",
      "1789 1 1\n",
      "1790 1 1\n",
      "1791 1 1\n",
      "1792 1 1\n",
      "1793 1 1\n",
      "1794 1 1\n",
      "1795 1 1\n",
      "1796 1 1\n",
      "1797 1 1\n",
      "1798 1 1\n",
      "1799 1 1\n",
      "1800 1 1\n",
      "1801 1 1\n",
      "1802 1 1\n",
      "1803 1 1\n",
      "1804 1 1\n",
      "1805 1 1\n",
      "1806 1 1\n",
      "1807 1 1\n",
      "1808 1 1\n",
      "1809 1 1\n",
      "1810 1 1\n",
      "1811 1 1\n",
      "1812 1 1\n",
      "1813 1 1\n",
      "1814 1 1\n",
      "1815 1 1\n",
      "1816 1 1\n",
      "1817 1 1\n",
      "1818 1 1\n",
      "1819 1 1\n",
      "1820 1 1\n",
      "1821 1 1\n",
      "1822 1 1\n",
      "1823 1 1\n",
      "1824 1 1\n",
      "1825 1 1\n",
      "1826 1 1\n",
      "1827 1 1\n",
      "1828 1 1\n",
      "1829 1 1\n",
      "1830 1 1\n",
      "1831 1 1\n",
      "1832 1 1\n",
      "1833 1 1\n",
      "1834 1 1\n",
      "1835 1 1\n",
      "1836 1 1\n",
      "1837 1 1\n",
      "1838 1 1\n",
      "1839 1 1\n",
      "1840 1 1\n",
      "1841 1 1\n",
      "1842 1 1\n",
      "1843 1 1\n",
      "1844 1 1\n",
      "1845 1 1\n",
      "1846 1 1\n",
      "1847 1 1\n",
      "1848 1 1\n",
      "1849 1 1\n",
      "1850 1 1\n",
      "1851 1 1\n",
      "1852 1 1\n",
      "1853 1 1\n",
      "1854 1 1\n",
      "1855 1 1\n",
      "1856 1 1\n",
      "1857 1 1\n",
      "1858 1 1\n",
      "1859 1 1\n",
      "1860 1 1\n",
      "1861 1 1\n",
      "1862 1 1\n",
      "1863 1 1\n",
      "1864 1 1\n",
      "1865 1 1\n",
      "1866 1 1\n",
      "1867 1 1\n",
      "1868 1 1\n",
      "1869 1 1\n",
      "1870 1 1\n",
      "1871 1 1\n",
      "1872 1 1\n",
      "1873 1 1\n",
      "1874 1 1\n",
      "1875 1 1\n",
      "1876 1 1\n",
      "1877 1 1\n",
      "1878 1 1\n",
      "1879 1 1\n",
      "1880 1 1\n",
      "1881 1 1\n",
      "1882 1 1\n",
      "1883 1 1\n",
      "1884 1 1\n",
      "1885 1 1\n",
      "1886 1 1\n",
      "1887 1 1\n",
      "1888 1 1\n",
      "1889 1 1\n",
      "1890 1 1\n",
      "1891 1 1\n",
      "1892 1 1\n",
      "1893 1 1\n",
      "1894 1 1\n",
      "1895 1 1\n",
      "1896 1 1\n",
      "1897 1 1\n",
      "1898 1 1\n",
      "1899 1 1\n",
      "1900 1 1\n",
      "1901 1 1\n",
      "1902 1 1\n",
      "1903 1 1\n",
      "1904 1 1\n",
      "1905 1 1\n",
      "1906 1 1\n",
      "1907 1 1\n",
      "1908 1 1\n",
      "1909 1 1\n",
      "1910 1 1\n",
      "1911 1 1\n",
      "1912 1 1\n",
      "1913 1 1\n",
      "1914 1 1\n",
      "1915 1 1\n",
      "1916 1 1\n",
      "1917 1 1\n",
      "1918 1 1\n",
      "1919 1 1\n",
      "1920 1 1\n",
      "1921 1 1\n",
      "1922 1 1\n",
      "1923 1 1\n",
      "1924 1 1\n",
      "1925 1 1\n",
      "1926 1 1\n",
      "1927 1 1\n",
      "1928 1 1\n",
      "1929 1 1\n",
      "1930 1 1\n",
      "1931 1 1\n",
      "1932 1 1\n",
      "1933 1 1\n",
      "1934 1 1\n",
      "1935 1 1\n",
      "1936 1 1\n",
      "1937 1 1\n",
      "1938 1 1\n",
      "1939 1 1\n",
      "1940 1 1\n",
      "1941 1 1\n",
      "1942 1 1\n",
      "1943 1 1\n",
      "1944 1 1\n",
      "1945 1 1\n",
      "1946 1 1\n",
      "1947 1 1\n",
      "1948 1 1\n",
      "1949 1 1\n",
      "1950 1 1\n",
      "1951 1 1\n",
      "1952 1 1\n",
      "1953 1 1\n",
      "1954 1 1\n",
      "1955 1 1\n",
      "1956 1 1\n",
      "1957 1 1\n",
      "1958 1 1\n",
      "1959 1 1\n",
      "1960 1 1\n",
      "1961 1 1\n",
      "1962 1 1\n",
      "1963 1 1\n",
      "1964 1 1\n",
      "1965 1 1\n",
      "1966 1 1\n",
      "1967 1 1\n",
      "1968 1 1\n",
      "1969 1 1\n",
      "1970 1 1\n",
      "1971 1 1\n",
      "1972 1 1\n",
      "1973 1 1\n",
      "1974 1 1\n",
      "1975 1 1\n",
      "1976 1 1\n",
      "1977 1 1\n",
      "1978 1 1\n",
      "1979 1 1\n",
      "1980 1 1\n",
      "1981 1 1\n",
      "1982 1 1\n",
      "1983 1 1\n",
      "1984 1 1\n",
      "1985 1 1\n",
      "1986 1 1\n",
      "1987 1 1\n",
      "1988 1 1\n",
      "1989 1 1\n",
      "1990 1 1\n",
      "1991 1 1\n",
      "1992 1 1\n",
      "1993 1 1\n",
      "1994 1 1\n",
      "1995 1 1\n",
      "1996 1 1\n",
      "1997 1 1\n",
      "1998 1 1\n",
      "1999 1 1\n",
      "2000 1 1\n",
      "2001 1 1\n",
      "2002 1 1\n",
      "2003 1 1\n",
      "2004 1 1\n",
      "2005 1 1\n",
      "2006 1 1\n",
      "2007 1 1\n",
      "2008 1 1\n",
      "2009 1 1\n",
      "2010 1 1\n",
      "2011 1 1\n",
      "2012 1 1\n",
      "2013 1 1\n",
      "2014 1 1\n",
      "2015 1 1\n",
      "2016 1 1\n",
      "2017 1 1\n",
      "2018 1 1\n",
      "2019 1 1\n",
      "2020 1 1\n",
      "2021 1 1\n",
      "2022 1 1\n",
      "2023 1 1\n",
      "2024 1 1\n",
      "2025 1 1\n",
      "2026 1 1\n",
      "2027 1 1\n",
      "2028 1 1\n",
      "2029 1 1\n",
      "2030 1 1\n",
      "2031 1 1\n",
      "2032 1 1\n",
      "2033 1 1\n",
      "2034 1 1\n",
      "2035 1 1\n",
      "2036 1 1\n",
      "2037 1 1\n",
      "2038 1 1\n",
      "2039 1 1\n",
      "2040 1 1\n",
      "2041 1 1\n",
      "2042 1 1\n",
      "2043 1 1\n",
      "2044 1 1\n",
      "2045 1 1\n",
      "2046 1 1\n",
      "2047 1 1\n",
      "2048 1 1\n",
      "2049 1 1\n",
      "2050 1 1\n",
      "2051 1 1\n",
      "2052 1 1\n",
      "2053 1 1\n",
      "2054 1 1\n",
      "2055 1 1\n",
      "2056 1 1\n",
      "2057 1 1\n",
      "2058 1 1\n",
      "2059 1 1\n",
      "2060 1 1\n",
      "2061 1 1\n",
      "2062 1 1\n",
      "2063 1 1\n",
      "2064 1 1\n",
      "2065 1 1\n",
      "2066 1 1\n",
      "2067 1 1\n",
      "2068 1 1\n",
      "2069 1 1\n",
      "2070 1 1\n",
      "2071 1 1\n",
      "2072 1 1\n",
      "2073 1 1\n",
      "2074 1 1\n",
      "2075 1 1\n",
      "2076 1 1\n",
      "2077 1 1\n",
      "2078 1 1\n",
      "2079 1 1\n",
      "2080 1 1\n",
      "2081 1 1\n",
      "2082 1 1\n",
      "2083 1 1\n",
      "2084 1 1\n",
      "2085 1 1\n",
      "2086 1 1\n",
      "2087 1 1\n",
      "2088 1 1\n",
      "2089 1 1\n",
      "2090 1 1\n",
      "2091 1 1\n",
      "2092 1 1\n",
      "2093 1 1\n",
      "2094 1 1\n",
      "2095 1 1\n",
      "2096 1 1\n",
      "2097 1 1\n",
      "2098 1 1\n",
      "2099 1 1\n",
      "2100 1 1\n",
      "2101 1 1\n",
      "2102 1 1\n",
      "2103 1 1\n",
      "2104 1 1\n",
      "2105 1 1\n",
      "2106 1 1\n",
      "2107 1 1\n",
      "2108 1 1\n",
      "2109 1 1\n",
      "2110 1 1\n",
      "2111 1 1\n",
      "2112 1 1\n",
      "2113 1 1\n",
      "2114 1 1\n",
      "2115 1 1\n",
      "2116 1 1\n",
      "2117 1 1\n",
      "2118 1 1\n",
      "2119 1 1\n",
      "2120 1 1\n",
      "2121 1 1\n",
      "2122 1 1\n",
      "2123 1 1\n",
      "2124 1 1\n",
      "2125 1 1\n",
      "2126 1 1\n",
      "2127 1 1\n",
      "2128 1 1\n",
      "2129 1 1\n",
      "2130 1 1\n",
      "2131 1 1\n",
      "2132 1 1\n",
      "2133 1 1\n",
      "2134 1 1\n",
      "2135 1 1\n",
      "2136 1 1\n",
      "2137 1 1\n",
      "2138 1 1\n",
      "2139 1 1\n",
      "2140 1 1\n",
      "2141 1 1\n",
      "2142 1 1\n",
      "2143 1 1\n",
      "2144 1 1\n",
      "2145 1 1\n",
      "2146 1 1\n",
      "2147 1 1\n",
      "2148 1 1\n",
      "2149 1 1\n",
      "2150 1 1\n",
      "2151 1 1\n",
      "2152 1 1\n",
      "2153 1 1\n",
      "2154 1 1\n",
      "2155 1 1\n",
      "2156 1 1\n",
      "2157 1 1\n",
      "2158 1 1\n",
      "2159 1 1\n",
      "2160 1 1\n",
      "2161 1 1\n",
      "2162 1 1\n",
      "2163 1 1\n",
      "2164 1 1\n",
      "2165 1 1\n",
      "2166 1 1\n",
      "2167 1 1\n",
      "2168 1 1\n",
      "2169 1 1\n",
      "2170 1 1\n",
      "2171 1 1\n",
      "2172 1 1\n",
      "2173 1 1\n",
      "2174 1 1\n",
      "2175 1 1\n",
      "2176 1 1\n",
      "2177 1 1\n",
      "2178 1 1\n",
      "2179 1 1\n",
      "2180 1 1\n",
      "2181 1 1\n",
      "2182 1 1\n",
      "2183 1 1\n",
      "2184 1 1\n",
      "2185 1 1\n",
      "2186 1 1\n",
      "2187 1 1\n",
      "2188 1 1\n",
      "2189 1 1\n",
      "2190 1 1\n",
      "2191 1 1\n",
      "2192 1 1\n",
      "2193 1 1\n",
      "2194 1 1\n",
      "2195 1 1\n",
      "2196 1 1\n",
      "2197 1 1\n",
      "2198 1 1\n",
      "2199 1 1\n",
      "2200 1 1\n",
      "2201 1 1\n",
      "2202 1 1\n",
      "2203 1 1\n",
      "2204 1 1\n",
      "2205 1 1\n",
      "2206 1 1\n",
      "2207 1 1\n",
      "2208 1 1\n",
      "2209 1 1\n",
      "2210 1 1\n",
      "2211 1 1\n",
      "2212 1 1\n",
      "2213 1 1\n",
      "2214 1 1\n",
      "2215 1 1\n",
      "2216 1 1\n",
      "2217 1 1\n",
      "2218 1 1\n",
      "2219 1 1\n",
      "2220 1 1\n",
      "2221 1 1\n",
      "2222 1 1\n",
      "2223 1 1\n",
      "2224 1 1\n",
      "2225 1 1\n",
      "2226 1 1\n",
      "2227 1 1\n",
      "2228 1 1\n",
      "2229 1 1\n",
      "2230 1 1\n",
      "2231 1 1\n",
      "2232 1 1\n",
      "2233 1 1\n",
      "2234 1 1\n",
      "2235 1 1\n",
      "2236 1 1\n",
      "2237 1 1\n",
      "2238 1 1\n",
      "2239 1 1\n",
      "2240 1 1\n",
      "2241 1 1\n",
      "2242 1 1\n",
      "2243 1 1\n",
      "2244 1 1\n",
      "2245 1 1\n",
      "2246 1 1\n",
      "2247 1 1\n",
      "2248 1 1\n",
      "2249 1 1\n",
      "2250 1 1\n",
      "2251 1 1\n",
      "2252 1 1\n",
      "2253 1 1\n",
      "2254 1 1\n",
      "2255 1 1\n",
      "2256 1 1\n",
      "2257 1 1\n",
      "2258 1 1\n",
      "2259 1 1\n",
      "2260 1 1\n",
      "2261 1 1\n",
      "2262 1 1\n",
      "2263 1 1\n",
      "2264 1 1\n",
      "2265 1 1\n",
      "2266 1 1\n",
      "2267 1 1\n",
      "2268 1 1\n",
      "2269 1 1\n",
      "2270 1 1\n",
      "2271 1 1\n",
      "2272 1 1\n",
      "2273 1 1\n",
      "2274 1 1\n",
      "2275 1 1\n",
      "2276 1 1\n",
      "2277 1 1\n",
      "2278 1 1\n",
      "2279 1 1\n",
      "2280 1 1\n",
      "2281 1 1\n",
      "2282 1 1\n",
      "2283 1 1\n",
      "2284 1 1\n",
      "2285 1 1\n",
      "2286 1 1\n",
      "2287 1 1\n",
      "2288 1 1\n",
      "2289 1 1\n",
      "2290 1 1\n",
      "2291 1 1\n",
      "2292 1 1\n",
      "2293 1 1\n",
      "2294 1 1\n",
      "2295 1 1\n",
      "2296 1 1\n",
      "2297 1 1\n",
      "2298 1 1\n",
      "2299 1 1\n",
      "2300 1 1\n",
      "2301 1 1\n",
      "2302 1 1\n",
      "2303 1 1\n",
      "2304 1 1\n",
      "2305 1 1\n",
      "2306 1 1\n",
      "2307 1 1\n",
      "2308 1 1\n",
      "2309 1 1\n",
      "2310 1 1\n",
      "2311 1 1\n",
      "2312 1 1\n",
      "2313 1 1\n",
      "2314 1 1\n",
      "2315 1 1\n",
      "2316 1 1\n",
      "2317 1 1\n",
      "2318 1 1\n",
      "2319 1 1\n",
      "2320 1 1\n",
      "2321 1 1\n",
      "2322 1 1\n",
      "2323 1 1\n",
      "2324 1 1\n",
      "2325 1 1\n",
      "2326 1 1\n",
      "2327 1 1\n",
      "2328 1 1\n",
      "2329 1 1\n",
      "2330 1 1\n",
      "2331 1 1\n",
      "2332 1 1\n",
      "2333 1 1\n",
      "2334 1 1\n",
      "2335 1 1\n",
      "2336 1 1\n",
      "2337 1 1\n",
      "2338 1 1\n",
      "2339 1 1\n",
      "2340 1 1\n",
      "2341 1 1\n",
      "2342 1 1\n",
      "2343 1 1\n",
      "2344 1 1\n",
      "2345 1 1\n",
      "2346 1 1\n",
      "2347 1 1\n",
      "2348 1 1\n",
      "2349 1 1\n",
      "2350 1 1\n",
      "2351 1 1\n",
      "2352 1 1\n",
      "2353 1 1\n",
      "2354 1 1\n",
      "2355 1 1\n",
      "2356 1 1\n",
      "2357 1 1\n",
      "2358 1 1\n",
      "2359 1 1\n",
      "2360 1 1\n",
      "2361 1 1\n",
      "2362 1 1\n",
      "2363 1 1\n",
      "2364 1 1\n",
      "2365 1 1\n",
      "2366 1 1\n",
      "2367 1 1\n",
      "2368 1 1\n",
      "2369 1 1\n",
      "2370 1 1\n",
      "2371 1 1\n",
      "2372 1 1\n",
      "2373 1 1\n",
      "2374 1 1\n",
      "2375 1 1\n",
      "2376 1 1\n",
      "2377 1 1\n",
      "2378 1 1\n",
      "2379 1 1\n",
      "2380 1 1\n",
      "2381 1 1\n",
      "2382 1 1\n",
      "2383 1 1\n",
      "2384 1 1\n",
      "2385 1 1\n",
      "2386 1 1\n",
      "2387 1 1\n",
      "2388 1 1\n",
      "2389 1 1\n",
      "2390 1 1\n",
      "2391 1 1\n",
      "2392 1 1\n",
      "2393 1 1\n",
      "2394 1 1\n",
      "2395 1 1\n",
      "2396 1 1\n",
      "2397 1 1\n",
      "2398 1 1\n",
      "2399 1 1\n",
      "2400 1 1\n",
      "2401 1 1\n",
      "2402 1 1\n",
      "2403 1 1\n",
      "2404 1 1\n",
      "2405 1 1\n",
      "2406 1 1\n",
      "2407 1 1\n",
      "2408 1 1\n",
      "2409 1 1\n",
      "2410 1 1\n",
      "2411 1 1\n",
      "2412 1 1\n",
      "2413 1 1\n",
      "2414 1 1\n",
      "2415 1 1\n",
      "2416 1 1\n",
      "2417 1 1\n",
      "2418 1 1\n",
      "2419 1 1\n",
      "2420 1 1\n",
      "2421 1 1\n",
      "2422 1 1\n",
      "2423 1 1\n",
      "2424 1 1\n",
      "2425 1 1\n",
      "2426 1 1\n",
      "2427 1 1\n",
      "2428 1 1\n",
      "2429 1 1\n",
      "2430 1 1\n",
      "2431 1 1\n",
      "2432 1 1\n",
      "2433 1 1\n",
      "2434 1 1\n",
      "2435 1 1\n",
      "2436 1 1\n",
      "2437 1 1\n",
      "2438 1 1\n",
      "2439 1 1\n",
      "2440 1 1\n",
      "2441 1 1\n",
      "2442 1 1\n",
      "2443 1 1\n",
      "2444 1 1\n",
      "2445 1 1\n",
      "2446 1 1\n",
      "2447 1 1\n",
      "2448 1 1\n",
      "2449 1 1\n",
      "2450 1 1\n",
      "2451 1 1\n",
      "2452 1 1\n",
      "2453 1 1\n",
      "2454 1 1\n",
      "2455 1 1\n",
      "2456 1 1\n",
      "2457 1 1\n",
      "2458 1 1\n",
      "2459 1 1\n",
      "2460 1 1\n",
      "2461 1 1\n",
      "2462 1 1\n",
      "2463 1 1\n",
      "2464 1 1\n",
      "2465 1 1\n",
      "2466 1 1\n",
      "2467 1 1\n",
      "2468 1 1\n",
      "2469 1 1\n",
      "2470 1 1\n",
      "2471 1 1\n",
      "2472 1 1\n",
      "2473 1 1\n",
      "2474 1 1\n",
      "2475 1 1\n",
      "2476 1 1\n",
      "2477 1 1\n",
      "2478 1 1\n",
      "2479 1 1\n",
      "2480 1 1\n",
      "2481 1 1\n",
      "2482 1 1\n",
      "2483 1 1\n",
      "2484 1 1\n",
      "2485 1 1\n",
      "2486 1 1\n",
      "2487 1 1\n",
      "2488 1 1\n",
      "2489 1 1\n",
      "2490 1 1\n",
      "2491 1 1\n",
      "2492 1 1\n",
      "2493 1 1\n",
      "2494 1 1\n",
      "2495 1 1\n",
      "2496 1 1\n",
      "2497 1 1\n",
      "2498 1 1\n",
      "2499 1 1\n",
      "2500 1 1\n",
      "2501 1 1\n",
      "2502 1 1\n",
      "2503 1 1\n",
      "2504 1 1\n",
      "2505 1 1\n",
      "2506 1 1\n",
      "2507 1 1\n",
      "2508 1 1\n",
      "2509 1 1\n",
      "2510 1 1\n",
      "2511 1 1\n",
      "2512 1 1\n",
      "2513 1 1\n",
      "2514 1 1\n",
      "2515 1 1\n",
      "2516 1 1\n",
      "2517 1 1\n",
      "2518 1 1\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2519 1 1\n",
      "2520 1 1\n",
      "2521 1 1\n",
      "2522 1 1\n",
      "2523 1 1\n",
      "2524 1 1\n",
      "2525 1 1\n",
      "2526 1 1\n",
      "2527 1 1\n",
      "2528 1 1\n",
      "2529 1 1\n",
      "2530 1 1\n",
      "2531 1 1\n",
      "2532 1 1\n",
      "2533 1 1\n",
      "2534 1 1\n",
      "2535 1 1\n",
      "2536 1 1\n",
      "2537 1 1\n",
      "2538 1 1\n",
      "2539 1 1\n",
      "2540 1 1\n",
      "2541 1 1\n",
      "2542 1 1\n",
      "2543 1 1\n",
      "2544 1 1\n",
      "2545 1 1\n",
      "2546 1 1\n",
      "2547 1 1\n",
      "2548 1 1\n",
      "2549 1 1\n",
      "2550 1 1\n",
      "2551 1 1\n",
      "2552 1 1\n",
      "2553 1 1\n",
      "2554 1 1\n",
      "2555 1 1\n",
      "2556 1 1\n",
      "2557 1 1\n",
      "2558 1 1\n",
      "2559 1 1\n",
      "2560 1 1\n",
      "2561 1 1\n",
      "2562 1 1\n",
      "2563 1 1\n",
      "2564 1 1\n",
      "2565 1 1\n",
      "2566 1 1\n",
      "2567 1 1\n",
      "2568 1 1\n",
      "2569 1 1\n",
      "2570 1 1\n",
      "2571 1 1\n",
      "2572 1 1\n",
      "2573 1 1\n",
      "2574 1 1\n",
      "2575 1 1\n",
      "2576 1 1\n",
      "2577 1 1\n",
      "2578 1 1\n",
      "2579 1 1\n",
      "2580 1 1\n",
      "2581 1 1\n",
      "2582 1 1\n",
      "2583 1 1\n",
      "2584 1 1\n",
      "2585 1 1\n",
      "2586 1 1\n",
      "2587 1 1\n",
      "2588 1 1\n",
      "2589 1 1\n",
      "2590 1 1\n",
      "2591 1 1\n",
      "2592 1 1\n",
      "2593 1 1\n",
      "2594 1 1\n",
      "2595 1 1\n",
      "2596 1 1\n",
      "2597 1 1\n",
      "2598 1 1\n",
      "2599 1 1\n",
      "2600 1 1\n",
      "2601 1 1\n",
      "2602 1 1\n",
      "2603 1 1\n",
      "2604 1 1\n",
      "2605 1 1\n",
      "2606 1 1\n",
      "2607 1 1\n",
      "2608 1 1\n",
      "2609 1 1\n",
      "2610 1 1\n",
      "2611 1 1\n",
      "2612 1 1\n",
      "2613 1 1\n",
      "2614 1 1\n",
      "2615 1 1\n",
      "2616 1 1\n",
      "2617 1 1\n",
      "2618 1 1\n",
      "2619 1 1\n",
      "2620 1 1\n",
      "2621 1 1\n",
      "2622 1 1\n",
      "2623 1 1\n",
      "2624 1 1\n",
      "2625 1 1\n",
      "2626 1 1\n",
      "2627 1 1\n",
      "2628 1 1\n",
      "2629 1 1\n",
      "2630 1 1\n",
      "2631 1 1\n",
      "2632 1 1\n",
      "2633 1 1\n",
      "2634 1 1\n",
      "2635 1 1\n",
      "2636 1 1\n",
      "2637 1 1\n",
      "2638 1 1\n",
      "2639 1 1\n",
      "2640 1 1\n",
      "2641 1 1\n",
      "2642 1 1\n",
      "2643 1 1\n",
      "2644 1 1\n",
      "2645 1 1\n",
      "2646 1 1\n",
      "2647 1 1\n",
      "2648 1 1\n",
      "2649 1 1\n",
      "2650 1 1\n",
      "2651 1 1\n",
      "2652 1 1\n",
      "2653 1 1\n",
      "2654 1 1\n",
      "2655 1 1\n",
      "2656 1 1\n",
      "2657 1 1\n",
      "2658 1 1\n",
      "2659 1 1\n",
      "2660 1 1\n",
      "2661 1 1\n",
      "2662 1 1\n",
      "2663 1 1\n",
      "2664 1 1\n",
      "2665 1 1\n",
      "2666 1 1\n",
      "2667 1 1\n",
      "2668 1 1\n",
      "2669 1 1\n",
      "2670 1 1\n",
      "2671 1 1\n",
      "2672 1 1\n",
      "2673 1 1\n",
      "2674 1 1\n",
      "2675 1 1\n",
      "2676 1 1\n",
      "2677 1 1\n",
      "2678 1 1\n",
      "2679 1 1\n",
      "2680 1 1\n",
      "2681 1 1\n",
      "2682 1 1\n",
      "2683 1 1\n",
      "2684 1 1\n",
      "2685 1 1\n",
      "2686 1 1\n",
      "2687 1 1\n",
      "2688 1 1\n",
      "2689 1 1\n",
      "2690 1 1\n",
      "2691 1 1\n",
      "2692 1 1\n",
      "2693 1 1\n",
      "2694 1 1\n",
      "2695 1 1\n",
      "2696 1 1\n",
      "2697 1 1\n",
      "2698 1 1\n",
      "2699 1 1\n",
      "2700 1 1\n",
      "2701 1 1\n",
      "2702 1 1\n",
      "2703 1 1\n",
      "2704 1 1\n",
      "2705 1 1\n",
      "2706 1 1\n",
      "2707 1 1\n",
      "2708 1 1\n",
      "2709 1 1\n",
      "2710 1 1\n",
      "2711 1 1\n",
      "2712 1 1\n",
      "2713 1 1\n",
      "2714 1 1\n",
      "2715 1 1\n",
      "2716 1 1\n",
      "2717 1 1\n",
      "2718 1 1\n",
      "2719 1 1\n",
      "2720 1 1\n",
      "2721 1 1\n",
      "2722 1 1\n",
      "2723 1 1\n",
      "2724 1 1\n",
      "2725 1 1\n",
      "2726 1 1\n",
      "2727 1 1\n",
      "2728 1 1\n",
      "2729 1 1\n",
      "2730 1 1\n",
      "2731 1 1\n",
      "2732 1 1\n",
      "2733 1 1\n",
      "2734 1 1\n",
      "2735 1 1\n",
      "2736 1 1\n",
      "2737 1 1\n",
      "2738 1 1\n",
      "2739 1 1\n",
      "2740 1 1\n",
      "2741 1 1\n",
      "2742 1 1\n",
      "2743 1 1\n",
      "2744 1 1\n",
      "2745 1 1\n",
      "2746 1 1\n",
      "2747 1 1\n",
      "2748 1 1\n",
      "2749 1 1\n",
      "2750 1 1\n",
      "2751 1 1\n",
      "2752 1 1\n",
      "2753 1 1\n",
      "2754 1 1\n",
      "2755 1 1\n",
      "2756 1 1\n",
      "2757 1 1\n",
      "2758 1 1\n",
      "2759 1 1\n",
      "2760 1 1\n",
      "2761 1 1\n",
      "2762 1 1\n",
      "2763 1 1\n",
      "2764 1 1\n",
      "2765 1 1\n",
      "2766 1 1\n",
      "2767 1 1\n",
      "2768 1 1\n",
      "2769 1 1\n",
      "2770 1 1\n",
      "2771 1 1\n",
      "2772 1 1\n",
      "2773 1 1\n",
      "2774 1 1\n",
      "2775 1 1\n",
      "2776 1 1\n",
      "2777 1 1\n",
      "2778 1 1\n",
      "2779 1 1\n",
      "2780 1 1\n",
      "2781 1 1\n",
      "2782 1 1\n",
      "2783 1 1\n",
      "2784 1 1\n",
      "2785 1 1\n",
      "2786 1 1\n",
      "2787 1 1\n",
      "2788 1 1\n",
      "2789 1 1\n",
      "2790 1 1\n",
      "2791 1 1\n",
      "2792 1 1\n",
      "2793 1 1\n",
      "2794 1 1\n",
      "2795 1 1\n",
      "2796 1 1\n",
      "2797 1 1\n",
      "2798 1 1\n",
      "2799 1 1\n",
      "2800 1 1\n",
      "2801 1 1\n",
      "2802 1 1\n",
      "2803 1 1\n",
      "2804 1 1\n",
      "2805 1 1\n",
      "2806 1 1\n",
      "2807 1 1\n",
      "2808 1 1\n",
      "2809 1 1\n",
      "2810 1 1\n",
      "2811 1 1\n",
      "2812 1 1\n",
      "2813 1 1\n",
      "2814 1 1\n",
      "2815 1 1\n",
      "2816 1 1\n",
      "2817 1 1\n",
      "2818 1 1\n",
      "2819 1 1\n",
      "2820 1 1\n",
      "2821 1 1\n",
      "2822 1 1\n",
      "2823 1 1\n",
      "2824 1 1\n",
      "2825 1 1\n",
      "2826 1 1\n",
      "2827 1 1\n",
      "2828 1 1\n",
      "2829 1 1\n",
      "2830 1 1\n",
      "2831 1 1\n",
      "2832 1 1\n",
      "2833 1 1\n",
      "2834 1 1\n",
      "2835 1 1\n",
      "2836 1 1\n",
      "2837 1 1\n",
      "2838 1 1\n",
      "2839 1 1\n",
      "2840 1 1\n",
      "2841 1 1\n",
      "2842 1 1\n",
      "2843 1 1\n",
      "2844 1 1\n",
      "2845 1 1\n",
      "2846 1 1\n",
      "2847 1 1\n",
      "2848 1 1\n",
      "2849 1 1\n",
      "2850 1 1\n",
      "2851 1 1\n",
      "2852 1 1\n",
      "2853 1 1\n",
      "2854 1 1\n",
      "2855 1 1\n",
      "2856 1 1\n",
      "2857 1 1\n",
      "2858 1 1\n",
      "2859 1 1\n",
      "2860 1 1\n",
      "2861 1 1\n",
      "2862 1 1\n",
      "2863 1 1\n",
      "2864 1 1\n",
      "2865 1 1\n",
      "2866 1 1\n",
      "2867 1 1\n",
      "2868 1 1\n",
      "2869 1 1\n",
      "2870 1 1\n",
      "2871 1 1\n",
      "2872 1 1\n",
      "2873 1 1\n",
      "2874 1 1\n",
      "2875 1 1\n",
      "2876 1 1\n",
      "2877 1 1\n",
      "2878 1 1\n",
      "2879 1 1\n",
      "2880 1 1\n",
      "2881 1 1\n",
      "2882 1 1\n",
      "2883 1 1\n",
      "2884 1 1\n",
      "2885 1 1\n",
      "2886 1 1\n",
      "2887 1 1\n",
      "2888 1 1\n",
      "2889 1 1\n",
      "2890 1 1\n",
      "2891 1 1\n",
      "2892 1 1\n",
      "2893 1 1\n",
      "2894 1 1\n",
      "2895 1 1\n",
      "2896 1 1\n",
      "2897 1 1\n",
      "2898 1 1\n",
      "2899 1 1\n",
      "2900 1 1\n",
      "2901 1 1\n",
      "2902 1 1\n",
      "2903 1 1\n",
      "2904 1 1\n",
      "2905 1 1\n",
      "2906 1 1\n",
      "2907 1 1\n",
      "2908 1 1\n",
      "2909 1 1\n",
      "2910 1 1\n",
      "2911 1 1\n",
      "2912 1 1\n",
      "2913 1 1\n",
      "2914 1 1\n",
      "2915 1 1\n",
      "2916 1 1\n",
      "2917 1 1\n",
      "2918 1 1\n",
      "2919 1 1\n",
      "2920 1 1\n",
      "2921 1 1\n",
      "2922 1 1\n",
      "2923 1 1\n",
      "2924 1 1\n",
      "2925 1 1\n",
      "2926 1 1\n",
      "2927 1 1\n",
      "2928 1 1\n",
      "2929 1 1\n",
      "2930 1 1\n",
      "2931 1 1\n",
      "2932 1 1\n",
      "2933 1 1\n",
      "2934 1 1\n",
      "2935 1 1\n",
      "2936 1 1\n",
      "2937 1 1\n",
      "2938 1 1\n",
      "2939 1 1\n",
      "2940 1 1\n",
      "2941 1 1\n",
      "2942 1 1\n",
      "2943 1 1\n",
      "2944 1 1\n",
      "2945 1 1\n",
      "2946 1 1\n",
      "2947 1 1\n",
      "2948 1 1\n",
      "2949 1 1\n",
      "2950 1 1\n",
      "2951 1 1\n",
      "2952 1 1\n",
      "2953 1 1\n",
      "2954 1 1\n",
      "2955 1 1\n",
      "2956 1 1\n",
      "2957 1 1\n",
      "2958 1 1\n",
      "2959 1 1\n",
      "2960 1 1\n",
      "2961 1 1\n",
      "2962 1 1\n",
      "2963 1 1\n",
      "2964 1 1\n",
      "2965 1 1\n",
      "2966 1 1\n",
      "2967 1 1\n",
      "2968 1 1\n",
      "2969 1 1\n",
      "2970 1 1\n",
      "2971 1 1\n",
      "2972 1 1\n",
      "2973 1 1\n",
      "2974 1 1\n",
      "2975 1 1\n",
      "2976 1 1\n",
      "2977 1 1\n",
      "2978 1 1\n",
      "2979 1 1\n",
      "2980 1 1\n",
      "2981 1 1\n",
      "2982 1 1\n",
      "2983 1 1\n",
      "2984 1 1\n",
      "2985 1 1\n",
      "2986 1 1\n",
      "2987 1 1\n",
      "2988 1 1\n",
      "2989 1 1\n",
      "2990 1 1\n",
      "2991 1 1\n",
      "2992 1 1\n",
      "2993 1 1\n",
      "2994 1 1\n",
      "2995 1 1\n",
      "2996 1 1\n",
      "2997 1 1\n",
      "2998 1 1\n",
      "2999 1 1\n",
      "3000 1 1\n",
      "3001 1 1\n",
      "3002 1 1\n",
      "3003 1 1\n",
      "3004 1 1\n",
      "3005 1 1\n",
      "3006 1 1\n",
      "3007 1 1\n",
      "3008 1 1\n",
      "3009 1 1\n",
      "3010 1 1\n",
      "3011 1 1\n",
      "3012 1 1\n",
      "3013 1 1\n",
      "3014 1 1\n",
      "3015 1 1\n",
      "3016 1 1\n",
      "3017 1 1\n",
      "3018 1 1\n",
      "3019 1 1\n",
      "3020 1 1\n",
      "3021 1 1\n",
      "3022 1 1\n",
      "3023 1 1\n",
      "3024 1 1\n",
      "3025 1 1\n",
      "3026 1 1\n",
      "3027 1 1\n",
      "3028 1 1\n",
      "3029 1 1\n",
      "3030 1 1\n",
      "3031 1 1\n",
      "3032 1 1\n",
      "3033 1 1\n",
      "3034 1 1\n",
      "3035 1 1\n",
      "3036 1 1\n",
      "3037 1 1\n",
      "3038 1 1\n",
      "3039 1 1\n",
      "3040 1 1\n",
      "3041 1 1\n",
      "3042 1 1\n",
      "3043 1 1\n",
      "3044 1 1\n",
      "3045 1 1\n",
      "3046 1 1\n",
      "3047 1 1\n",
      "3048 1 1\n",
      "3049 1 1\n",
      "3050 1 1\n",
      "3051 1 1\n",
      "3052 1 1\n",
      "3053 1 1\n",
      "3054 1 1\n",
      "3055 1 1\n",
      "3056 1 1\n",
      "3057 1 1\n",
      "3058 1 1\n",
      "3059 1 1\n",
      "3060 1 1\n",
      "3061 1 1\n",
      "3062 1 1\n",
      "3063 1 1\n",
      "3064 1 1\n",
      "3065 1 1\n",
      "3066 1 1\n",
      "3067 1 1\n",
      "3068 1 1\n",
      "3069 1 1\n",
      "3070 1 1\n",
      "3071 1 1\n",
      "3072 1 1\n",
      "3073 1 1\n",
      "3074 1 1\n",
      "3075 1 1\n",
      "3076 1 1\n",
      "3077 1 1\n",
      "3078 1 1\n",
      "3079 1 1\n",
      "3080 1 1\n",
      "3081 1 1\n",
      "3082 1 1\n",
      "3083 1 1\n",
      "3084 1 1\n",
      "3085 1 1\n",
      "3086 1 1\n",
      "3087 1 1\n",
      "3088 1 1\n",
      "3089 1 1\n",
      "3090 1 1\n",
      "3091 1 1\n",
      "3092 1 1\n",
      "3093 1 1\n",
      "3094 1 1\n",
      "3095 1 1\n",
      "3096 1 1\n",
      "3097 1 1\n",
      "3098 1 1\n",
      "3099 1 1\n",
      "3100 1 1\n",
      "3101 1 1\n",
      "3102 1 1\n",
      "3103 1 1\n",
      "3104 1 1\n",
      "3105 1 1\n",
      "3106 1 1\n",
      "3107 1 1\n",
      "3108 1 1\n",
      "3109 1 1\n",
      "3110 1 1\n",
      "3111 1 1\n",
      "3112 1 1\n",
      "3113 1 1\n",
      "3114 1 1\n",
      "3115 1 1\n",
      "3116 1 1\n",
      "3117 1 1\n",
      "3118 1 1\n",
      "3119 1 1\n",
      "3120 1 1\n",
      "3121 1 1\n",
      "3122 1 1\n",
      "3123 1 1\n",
      "3124 1 1\n",
      "3125 1 1\n",
      "3126 1 1\n",
      "3127 1 1\n",
      "3128 1 1\n",
      "3129 1 1\n",
      "3130 1 1\n",
      "3131 1 1\n",
      "3132 1 1\n",
      "3133 1 1\n",
      "3134 1 1\n",
      "3135 1 1\n",
      "3136 1 1\n",
      "3137 1 1\n",
      "3138 1 1\n",
      "3139 1 1\n",
      "3140 1 1\n",
      "3141 1 1\n",
      "3142 1 1\n",
      "3143 1 1\n",
      "3144 1 1\n",
      "3145 1 1\n",
      "3146 1 1\n",
      "3147 1 1\n",
      "3148 1 1\n",
      "3149 1 1\n",
      "3150 1 1\n",
      "3151 1 1\n",
      "3152 1 1\n",
      "3153 1 1\n",
      "3154 1 1\n",
      "3155 1 1\n",
      "3156 1 1\n",
      "3157 1 1\n",
      "3158 1 1\n",
      "3159 1 1\n",
      "3160 1 1\n",
      "3161 1 1\n",
      "3162 1 1\n",
      "3163 1 1\n",
      "3164 1 1\n",
      "3165 1 1\n",
      "3166 1 1\n",
      "3167 1 1\n",
      "3168 1 1\n",
      "3169 1 1\n",
      "3170 1 1\n",
      "3171 1 1\n",
      "3172 1 1\n",
      "3173 1 1\n",
      "3174 1 1\n",
      "3175 1 1\n",
      "3176 1 1\n",
      "3177 1 1\n",
      "3178 1 1\n",
      "3179 1 1\n",
      "3180 1 1\n",
      "3181 1 1\n",
      "3182 1 1\n",
      "3183 1 1\n",
      "3184 1 1\n",
      "3185 1 1\n",
      "3186 1 1\n",
      "3187 1 1\n",
      "3188 1 1\n",
      "3189 1 1\n",
      "3190 1 1\n",
      "3191 1 1\n",
      "3192 1 1\n",
      "3193 1 1\n",
      "3194 1 1\n",
      "3195 1 1\n",
      "3196 1 1\n",
      "3197 1 1\n",
      "3198 1 1\n",
      "3199 1 1\n",
      "3200 1 1\n",
      "3201 1 1\n",
      "3202 1 1\n",
      "3203 1 1\n",
      "3204 1 1\n",
      "3205 1 1\n",
      "3206 1 1\n",
      "3207 1 1\n",
      "3208 1 1\n",
      "3209 1 1\n",
      "3210 1 1\n",
      "3211 1 1\n",
      "3212 1 1\n",
      "3213 1 1\n",
      "3214 1 1\n",
      "3215 1 1\n",
      "3216 1 1\n",
      "3217 1 1\n",
      "3218 1 1\n",
      "3219 1 1\n",
      "3220 1 1\n",
      "3221 1 1\n",
      "3222 1 1\n",
      "3223 1 1\n",
      "3224 1 1\n",
      "3225 1 1\n",
      "3226 1 1\n",
      "3227 1 1\n",
      "3228 1 1\n",
      "3229 1 1\n",
      "3230 1 1\n",
      "3231 1 1\n",
      "3232 1 1\n",
      "3233 1 1\n",
      "3234 1 1\n",
      "3235 1 1\n",
      "3236 1 1\n",
      "3237 1 1\n",
      "3238 1 1\n",
      "3239 1 1\n",
      "3240 1 1\n",
      "3241 1 1\n",
      "3242 1 1\n",
      "3243 1 1\n",
      "3244 1 1\n",
      "3245 1 1\n",
      "3246 1 1\n",
      "3247 1 1\n",
      "3248 1 1\n",
      "3249 1 1\n",
      "3250 1 1\n",
      "3251 1 1\n",
      "3252 1 1\n",
      "3253 1 1\n",
      "3254 1 1\n",
      "3255 1 1\n",
      "3256 1 1\n",
      "3257 1 1\n",
      "3258 1 1\n",
      "3259 1 1\n",
      "3260 1 1\n",
      "3261 1 1\n",
      "3262 1 1\n",
      "3263 1 1\n",
      "3264 1 1\n",
      "3265 1 1\n",
      "3266 1 1\n",
      "3267 1 1\n",
      "3268 1 1\n",
      "3269 1 1\n",
      "3270 1 1\n",
      "3271 1 1\n",
      "3272 1 1\n",
      "3273 1 1\n",
      "3274 1 1\n",
      "3275 1 1\n",
      "3276 1 1\n",
      "3277 1 1\n",
      "3278 1 1\n",
      "3279 1 1\n",
      "3280 1 1\n",
      "3281 1 1\n",
      "3282 1 1\n",
      "3283 1 1\n",
      "3284 1 1\n",
      "3285 1 1\n",
      "3286 1 1\n",
      "3287 1 1\n",
      "3288 1 1\n",
      "3289 1 1\n",
      "3290 1 1\n",
      "3291 1 1\n",
      "3292 1 1\n",
      "3293 1 1\n",
      "3294 1 1\n",
      "3295 1 1\n",
      "3296 1 1\n",
      "3297 1 1\n",
      "3298 1 1\n",
      "3299 1 1\n",
      "3300 1 1\n",
      "3301 1 1\n",
      "3302 1 1\n",
      "3303 1 1\n",
      "3304 1 1\n",
      "3305 1 1\n",
      "3306 1 1\n",
      "3307 1 1\n",
      "3308 1 1\n",
      "3309 1 1\n",
      "3310 1 1\n",
      "3311 1 1\n",
      "3312 1 1\n",
      "3313 1 1\n",
      "3314 1 1\n",
      "3315 1 1\n",
      "3316 1 1\n",
      "3317 1 1\n",
      "3318 1 1\n",
      "3319 1 1\n",
      "3320 1 1\n",
      "3321 1 1\n",
      "3322 1 1\n",
      "3323 1 1\n",
      "3324 1 1\n",
      "3325 1 1\n",
      "3326 1 1\n",
      "3327 1 1\n",
      "3328 1 1\n",
      "3329 1 1\n",
      "3330 1 1\n",
      "3331 1 1\n",
      "3332 1 1\n",
      "3333 1 1\n",
      "3334 1 1\n",
      "3335 1 1\n",
      "3336 1 1\n",
      "3337 1 1\n",
      "3338 1 1\n",
      "3339 1 1\n",
      "3340 1 1\n",
      "3341 1 1\n",
      "3342 1 1\n",
      "3343 1 1\n",
      "3344 1 1\n",
      "3345 1 1\n",
      "3346 1 1\n",
      "3347 1 1\n",
      "3348 1 1\n",
      "3349 1 1\n",
      "3350 1 1\n",
      "3351 1 1\n",
      "3352 1 1\n",
      "3353 1 1\n",
      "3354 1 1\n",
      "3355 1 1\n",
      "3356 1 1\n",
      "3357 1 1\n",
      "3358 1 1\n",
      "3359 1 1\n",
      "3360 1 1\n",
      "3361 1 1\n",
      "3362 1 1\n",
      "3363 1 1\n",
      "3364 1 1\n",
      "3365 1 1\n",
      "3366 1 1\n",
      "3367 1 1\n",
      "3368 1 1\n",
      "3369 1 1\n",
      "3370 1 1\n",
      "3371 1 1\n",
      "3372 1 1\n",
      "3373 1 1\n",
      "3374 1 1\n",
      "3375 1 1\n",
      "3376 1 1\n",
      "3377 1 1\n",
      "3378 1 1\n",
      "3379 1 1\n",
      "3380 1 1\n",
      "3381 1 1\n",
      "3382 1 1\n",
      "3383 1 1\n",
      "3384 1 1\n",
      "3385 1 1\n",
      "3386 1 1\n",
      "3387 1 1\n",
      "3388 1 1\n",
      "3389 1 1\n",
      "3390 1 1\n",
      "3391 1 1\n",
      "3392 1 1\n",
      "3393 1 1\n",
      "3394 1 1\n",
      "3395 1 1\n",
      "3396 1 1\n",
      "3397 1 1\n",
      "3398 1 1\n",
      "3399 1 1\n",
      "3400 1 1\n",
      "3401 1 1\n",
      "3402 1 1\n",
      "3403 1 1\n",
      "3404 1 1\n",
      "3405 1 1\n",
      "3406 1 1\n",
      "3407 1 1\n",
      "3408 1 1\n",
      "3409 1 1\n",
      "3410 1 1\n",
      "3411 1 1\n",
      "3412 1 1\n",
      "3413 1 1\n",
      "3414 1 1\n",
      "3415 1 1\n",
      "3416 1 1\n",
      "3417 1 1\n",
      "3418 1 1\n",
      "3419 1 1\n",
      "3420 1 1\n",
      "3421 1 1\n",
      "3422 1 1\n",
      "3423 1 1\n",
      "3424 1 1\n",
      "3425 1 1\n",
      "3426 1 1\n",
      "3427 1 1\n",
      "3428 1 1\n",
      "3429 1 1\n",
      "3430 1 1\n",
      "3431 1 1\n",
      "3432 1 1\n",
      "3433 1 1\n",
      "3434 1 1\n",
      "3435 1 1\n",
      "3436 1 1\n",
      "3437 1 1\n",
      "3438 1 1\n",
      "3439 1 1\n",
      "3440 1 1\n",
      "3441 1 1\n",
      "3442 1 1\n",
      "3443 1 1\n",
      "3444 1 1\n",
      "3445 1 1\n",
      "3446 1 1\n",
      "3447 1 1\n",
      "3448 1 1\n",
      "3449 1 1\n",
      "3450 1 1\n",
      "3451 1 1\n",
      "3452 1 1\n",
      "3453 1 1\n",
      "3454 1 1\n",
      "3455 1 1\n",
      "3456 1 1\n",
      "3457 1 1\n",
      "3458 1 1\n",
      "3459 1 1\n",
      "3460 1 1\n",
      "3461 1 1\n",
      "3462 1 1\n",
      "3463 1 1\n",
      "3464 1 1\n",
      "3465 1 1\n",
      "3466 1 1\n",
      "3467 1 1\n",
      "3468 1 1\n",
      "3469 1 1\n",
      "3470 1 1\n",
      "3471 1 1\n",
      "3472 1 1\n",
      "3473 1 1\n",
      "3474 1 1\n",
      "3475 1 1\n",
      "3476 1 1\n",
      "3477 1 1\n",
      "3478 1 1\n",
      "3479 1 1\n",
      "3480 1 1\n",
      "3481 1 1\n",
      "3482 1 1\n",
      "3483 1 1\n",
      "3484 1 1\n",
      "3485 1 1\n",
      "3486 1 1\n",
      "3487 1 1\n",
      "3488 1 1\n",
      "3489 1 1\n",
      "3490 1 1\n",
      "3491 1 1\n",
      "3492 1 1\n",
      "3493 1 1\n",
      "3494 1 1\n",
      "3495 1 1\n",
      "3496 1 1\n",
      "3497 1 1\n",
      "3498 1 1\n",
      "3499 1 1\n",
      "3500 1 1\n",
      "3501 1 1\n",
      "3502 1 1\n",
      "3503 1 1\n",
      "3504 1 1\n",
      "3505 1 1\n",
      "3506 1 1\n",
      "3507 1 1\n",
      "3508 1 1\n",
      "3509 1 1\n",
      "3510 1 1\n",
      "3511 1 1\n",
      "3512 1 1\n",
      "3513 1 1\n",
      "3514 1 1\n",
      "3515 1 1\n",
      "3516 1 1\n",
      "3517 1 1\n",
      "3518 1 1\n",
      "3519 1 1\n",
      "3520 1 1\n",
      "3521 1 1\n",
      "3522 1 1\n",
      "3523 1 1\n",
      "3524 1 1\n",
      "3525 1 1\n",
      "3526 1 1\n",
      "3527 1 1\n",
      "3528 1 1\n",
      "3529 1 1\n",
      "3530 1 1\n",
      "3531 1 1\n",
      "3532 1 1\n",
      "3533 1 1\n",
      "3534 1 1\n",
      "3535 1 1\n",
      "3536 1 1\n",
      "3537 1 1\n",
      "3538 1 1\n",
      "3539 1 1\n",
      "3540 1 1\n",
      "3541 6959 1\n",
      "6959 * 8353 = 58128527\n"
     ]
    }
   ],
   "source": [
    "gcdPlus = 1\n",
    "gcdMinus = 1\n",
    "\n",
    "step = 1\n",
    "\n",
    "while gcdPlus == 1 and gcdMinus == 1:\n",
    "    x = random.randint(2, n)\n",
    "    y = random.randint(2, n)\n",
    "    gcdPlus = math.gcd((x+y) % n, n)\n",
    "    gcdMinus = math.gcd((x-y) % n, n)\n",
    "    print(step, gcdPlus, gcdMinus)\n",
    "    step = step + 1\n",
    "    \n",
    "if gcdPlus > 1:\n",
    "    print(gcdPlus,\"*\", n // gcdPlus, \"=\", n)\n",
    "else:\n",
    "    print(gcdMinus,\"*\", n // gcdMinus, \"=\", n)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}