{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e A random number generator (RNG) is a computational or physical device designed to generate a sequence of numbers or symbols that lack any pattern, i.e. appear random. Many of these have existed since ancient time, including dices, coin flipping, the shuffling of playing cards, and many other techniques. These methods depend on the measurement of some physical phenomenon which is expected to be random, and are still widely used today. On the other hand, deterministic computational algorithms were introduced into random number generation. Despite such algorithms\u0027 ability to produce apparently random results, they are in fact determined by a shorter initial value, known as a seed or key. These algorithms are often called pseudorandom number generators. They can also be called RNG customarily, but actually differ with real RNG significantly. \u003cbr\u003e Now considering a simple RNG, whose algorithm has two positive integer parameters A, B and a prime parameter M (2 ≤ A, B \u0026lt; M ≤ 10\u003csup\u003e18\u003c/sup\u003e). To run the algorithm, a seed X0 (0 ≤ X\u003csub\u003e0\u003c/sub\u003e \u0026lt; M) is required, and the algorithm produces a integer sequence Xn satisfying the condition X\u003csub\u003en\u003c/sub\u003e \u003d (A × X\u003csub\u003en - 1\u003c/sub\u003e + B) mod M for any positive integer n.\u003cbr\u003e An application implemented this algorithm. This application has another two parameters S (S ≤ M) and K (K ≤ 10\u003csup\u003e5\u003c/sup\u003e), and will use this RNG in such a way. Firstly, the application generates the first K integers in the random sequence including the seed, and these numbers modulo S are stored in another number sequence D, i.e. D\u003csub\u003ei\u003c/sub\u003e \u003d X\u003csub\u003ei\u003c/sub\u003e mod S for any integer i in [0, K - 1]. Then, another random integer X\u003csub\u003eK\u003c/sub\u003e is produced, and the application chooses the ((X\u003csub\u003eK\u003c/sub\u003e mod K) + 1)-th number in sequence D, i.e. D\u003csub\u003eXk mod K\u003c/sub\u003e as its output C. If an output C (0 ≤ C \u0026lt; S) is observed in a certain run, and parameters A, B, M, S, K is known, your task is determining a possible X0 which leads to the output C.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" There are at most 200 test cases. Each test case is a single line containing six integers, A, B, M, S, K and C, seperated by space. The meaning of these numbers are described above.\u003cbr\u003e The input is ended by 0 0 0 0 0 0\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":" You should output an integer for each test case, indicating a possible X\u003csub\u003e0\u003c/sub\u003e. If there is no solution, print \"impossible\" instead. This problem is special judged.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 2 97 5 3 2\r\n2 2 97 5 3 3\r\n0 0 0 0 0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n8\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}