The Buried Time Capsule

A school buried a time capsule in a field of width columns (numbered 1..width from west to east) and height rows (numbered 1..height from north to south), and nobody wrote down where. A ground scanner can answer two kinds of question:

• col_at_most(x) is True if the capsule lies in column x or further west (columns 1..x);
• row_at_most(y) is True if the capsule lies in row y or further north (rows 1..y).

Together you may ask at most ⌈log2 width⌉ + ⌈log2 height⌉ questions. One question too many raises TooManyQuestions.

Write find_capsule(width, height, col_at_most, row_at_most) that returns the capsule's position as a tuple (column, row).

The tests run with_scanner(find_capsule, width, height, seed), which hides the capsule and counts your questions. Try it with Run: print(with_scanner(find_capsule, 20, 30, 1)).

Examples

Input:  with_scanner(find_capsule, 8, 4, 1)   (a field of 8 x 4 plots; 3 + 2 = 5 questions)
Output: {"answer": ..., "questions": ..., "limit": 5, "capsule": ...}
        correct when answer == capsule

Input:  with_scanner(find_capsule, 1, 1, 2)   (only one plot: no question is needed)
Output: {"answer": (1, 1), "questions": 0, "limit": 0, "capsule": (1, 1)}

Constraints

• 1 <= width, height <= 10**9
• at most ⌈log2 width⌉ + ⌈log2 height⌉ questions in total
• a question outside the field (x not in 1..width, y not in 1..height) raises ValueError

Goals

• Split a two-dimensional search into two independent searches
• Share one question budget between two kinds of question