import java.util.*; import java.io.*; public class probedroids_font { public static void main(String[] args) throws Exception { PrintWriter out = new PrintWriter(System.out); new probedroids_font(new FastScanner(System.in), out); out.close(); } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } // Count the number points inside this triangle not including the line // from (0, 0) to (nRows, nCols) // // /| // / | // / | // / | // ------ // // Do this by creating the rectangle using those two points. // The number of lattice points is the number of points in the rectangle // (trivial to find) minus the number of points on the diagonal (gcd helps). // long countTriangle(int nRows, int nCols, boolean includeDiag) { int g = gcd(nRows, nCols); if (nRows == 0 || nCols == 0) return (includeDiag ? g : 0); long numRectangle = (nRows+1L) * (nCols+1L); long numTriangle = (numRectangle - g - 1) / 2; return numTriangle + (includeDiag ? g : 0); } // Tells you how many droids are destroyed strictly right of you long countLessThan(int region, int n, int m) { if (region == n+m-1) return n*1L*m-1; // If we are less than the number of rows do one thing. if (region < n) return countTriangle(region, m-1, false); // Past the midpoint use inclusion-exclusion (easier). long totalPoints = n * 1L * m - 1L; long trianglePoints = countTriangle(n-1, m-(region-n)-2, true); return totalPoints - trianglePoints; } // Returns all the points in a given slice. vec2[] getPointsForRegion(int region, int n, int m) { int numPoints = (int)(countLessThan(region+1, n, m) - countLessThan(region, n, m)); vec2[] res = new vec2[numPoints]; int ptr = 0; // n=1 doesn't work with this method, so I hack it. if (n == 1) { res[0] = new vec2(region+1, 0); return res; } if (region+1 < n) { // Construct the points off the x-axis long ex = m-1; long ey1 = region; long ey2 = ey1+1; for (int x=1; x<=m-1; x++) { long y1 = (ey1*x+ex-1)/ex; long y2 = (ey2*x-1)/ex; if (y1 == y2) res[ptr++] = new vec2(x, (int)y1); } } else { // Construct the points off the y-axis long ex1 = m-region+n-3; long ex2 = ex1+1; long ey = n-1; for (int y=1; y<=n-1; y++) { long x1 = (ex1*y+ey)/ey; long x2 = (ex2*y)/ey; if (x1 == x2) res[ptr++] = new vec2((int)x1, y); } } return res; } Random rnd = new Random(1337L); int randint(int i, int j) { int p = rnd.nextInt(j-i+1); return p+i; } void swap(vec2[] vs, int i, int j) { vec2 tmp = vs[i]; vs[i] = vs[j]; vs[j] = tmp; } public probedroids_font(FastScanner in, PrintWriter out) throws Exception { int n = in.nextInt(); int m = in.nextInt(); int q = in.nextInt(); while (q-->0) { long k = in.nextLong()-1; int lo = 0, hi = n+m; while (lo < hi) { int mid = (hi+lo+1) / 2; long rr = countLessThan(mid, n, m); if (rr <= k) lo = mid; else hi = mid-1; } int kk = (int)(k-countLessThan(lo, n, m)); vec2[] pts = getPointsForRegion(lo, n, m); // Find the kth point in the region using quickselect O(n) vec2 result = null; int start = 0; int end = pts.length-1; while (start < end) { int pivot = randint(start, end); swap(pts, end, pivot); int pivotIndex = start; for (int i=start; i { int x, y; long m; vec2(int xx, int yy) { x=xx; y=yy; m = x*1L*x + y*1L*y; } public int compareTo(vec2 rhs) { long cx = x*1L*rhs.y - y*1L*rhs.x; if (cx == 0) return Long.compare(m, rhs.m); return cx < 0 ? 1 : -1; } } class FastScanner{ private InputStream stream; private byte[] buf = new byte[1024]; private int curChar; private int numChars; public FastScanner(InputStream stream) { this.stream = stream; } int read() { if (numChars == -1) throw new InputMismatchException(); if (curChar >= numChars){ curChar = 0; try{ numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } boolean isSpaceChar(int c) { return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1; } boolean isEndline(int c) { return c=='\n'||c=='\r'||c==-1; } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String next(){ int c = read(); while (isSpaceChar(c)) c = read(); StringBuilder res = new StringBuilder(); do{ res.appendCodePoint(c); c = read(); }while(!isSpaceChar(c)); return res.toString(); } String nextLine(){ int c = read(); while (isEndline(c)) c = read(); StringBuilder res = new StringBuilder(); do{ res.appendCodePoint(c); c = read(); }while(!isEndline(c)); return res.toString(); } }