{"raw_statement":[{"iden":"problem statement","content":"You are given a positive real number $r$ less than $1$, and a positive integer $N$.\nAmong the pair of integers $(p,q)$ such that $0\\leq p\\leq q\\leq N$ and $\\gcd(p,q)=1$, find the one that minimizes $\\left\\vert r-\\dfrac pq\\right\\vert$.\nIf multiple such pairs $(p,q)$ exist, print the one with the smallest value of $\\dfrac pq$."},{"iden":"constraints","content":"*   $0\\lt r\\lt 1$\n*   $r$ is given as a real number with at most $18$ decimal places.\n*   $1\\leq N\\leq 10^{10}$\n*   $N$ is an integer."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$r$\n$N$"},{"iden":"sample input 1","content":"0.333\n33"},{"iden":"sample output 1","content":"1 3\n\n$\\left\\vert0.333-\\dfrac13\\right\\vert=\\dfrac1{3000}$. There is no $0\\leq p\\leq q\\leq33,\\gcd(p,q)=1$ such that $\\left\\vert0.333-\\dfrac pq\\right\\vert\\lt\\dfrac1{3000}$, so print `1 3`."},{"iden":"sample input 2","content":"0.45\n5"},{"iden":"sample output 2","content":"2 5\n\n$\\left\\vert0.45-\\dfrac12\\right\\vert=\\left\\vert0.45-\\dfrac25\\right\\vert=\\dfrac1{20}$. There is no $0\\leq p\\leq q\\leq5,\\gcd(p,q)=1$ such that $\\left\\vert0.45-\\dfrac pq\\right\\vert\\lt\\dfrac1{20}$, and we have $\\dfrac12\\gt\\dfrac25$, so print `2 5`."},{"iden":"sample input 3","content":"0.314159265358979323\n10000"},{"iden":"sample output 3","content":"71 226\n\n$\\left\\vert0.314159265358979323-\\dfrac{71}{226}\\right\\vert=\\dfrac{3014435336501}{113000000000000000000}$."},{"iden":"sample input 4","content":"0.007735339533561113\n7203576162"},{"iden":"sample output 4","content":"34928144 4515398949"}],"translated_statement":null,"sample_group":[],"show_order":["render_html"],"formal_statement":null,"simple_statement":null,"has_page_source":true}