Two kittens, Max and Min, play with a pair of non-negative integers x and y. As you can guess from their names, kitten Max loves to maximize and kitten Min loves to minimize. As part of this game Min wants to make sure that both numbers, x and y became negative at the same time, and kitten Max tries to prevent him from doing so.Each kitten has a set of pairs of integers available to it. Kitten Max has n pairs of non-negative integers (ai, bi) (1 ≤ i ≤ n), and kitten Min has m pairs of non-negative integers (cj, dj) (1 ≤ j ≤ m). As kitten Max makes a move, it can take any available pair (ai, bi) and add ai to x and bi to y, and kitten Min can take any available pair (cj, dj) and subtract cj from x and dj from y. Each kitten can use each pair multiple times during distinct moves.Max moves first. Kitten Min is winning if at some moment both numbers a, b are negative simultaneously. Otherwise, the winner of the game is kitten Max. Determine which kitten wins if both of them play optimally.InputThe first line contains two integers, n and m (1 ≤ n, m ≤ 100 000) — the number of pairs of numbers available to Max and Min, correspondingly.The second line contains two integers x, y (1 ≤ x, y ≤ 109) — the initial values of numbers with which the kittens are playing.Next n lines contain the pairs of numbers ai, bi (1 ≤ ai, bi ≤ 109) — the pairs available to Max.The last m lines contain pairs of numbers cj, dj (1 ≤ cj, dj ≤ 109) — the pairs available to Min.OutputPrint «Max» (without the quotes), if kitten Max wins, or "Min" (without the quotes), if kitten Min wins.

Alice and Bob came up with a rather strange game. They have an array of integers a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛. Alice chooses a certain integer k𝑘 and tells it to Bob, then the following happens:Bob chooses two integers i𝑖 and j𝑗 (1≤i<j≤n1≤𝑖<𝑗≤𝑛), and then finds the maximum among the integers ai,ai+1,…,aj𝑎𝑖,𝑎𝑖+1,…,𝑎𝑗;If the obtained maximum is strictly greater than k𝑘, Alice wins, otherwise Bob wins.Help Alice find the maximum k𝑘 at which she is guaranteed to win.InputEach test consists of multiple test cases. The first line contains a single integer t𝑡 (1≤t≤1041≤𝑡≤104) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer n𝑛 (2≤n≤5⋅1042≤𝑛≤5⋅104) — the number of elements in the array.The second line of each test case contains n𝑛 integers a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛 (1≤ai≤1091≤𝑎𝑖≤109) — the elements of the array.It is guaranteed that the sum of n𝑛 over all test cases does not exceed 5⋅1045⋅104.OutputFor each test case, output one integer — the maximum integer k𝑘 at which Alice is guaranteed to win.ExampleinputCopy642 4 1 751 2 3 4 521 1337 8 16510 10 10 10 9103 12 9 5 2 3 2 9 8 2outputCopy3101592NoteIn the first test case, all possible subsegments that Bob can choose look as follows: [2,4],[2,4,1],[2,4,1,7],[4,1],[4,1,7],[1,7][2,4],[2,4,1],[2,4,1,7],[4,1],[4,1,7],[1,7]. The maximums on the subsegments are respectively equal to 4,4,7,4,7,74,4,7,4,7,7. It can be shown that 33 is the largest integer such that any of the maximums will be strictly greater than it.In the third test case, the only segment that Bob can choose is [1,1][1,1]. So the answer is 00.

There is rectangle of size 𝑁×𝑀N×M with opposite corners at (0,0)(0,0) and (𝑁,𝑀)(N,M); and a special point (𝑥+0.5,𝑦+0.5) (0≤𝑥<𝑁,0≤𝑦<𝑀)(x+0.5,y+0.5) (0≤x<N,0≤y<M).Two players play a game on the rectangle where each player takes alternate turns. In his/her turn, the player will choose a line, either 𝑥=𝑘x=k or 𝑦=𝑘y=k, such that:𝑘k is an integer;The chosen line divides the current rectangle into two non-empty parts.The part of rectangle that does not consist of the special point, is discarded for further moves.The player who cannot make a move loses. If both players play optimally, determine the number of special points such that the first player wins.Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case contains two space-separated integers 𝑁N and 𝑀M — the lengths of the sides of the rectangle.Output FormatFor each test case, print the number of special points (𝑥+0.5,𝑦+0.5)(x+0.5,y+0.5) for which the first player wins the game.Note that 0≤𝑥<𝑁0≤x<N and 0≤𝑦<𝑀0≤y<M.Constraints1≤𝑇≤1041≤T≤10 4 1≤𝑁,𝑀≤1061≤N,M≤10 6 The sum of 𝑁N as well as the sum of 𝑀M over all test cases does not exceed 10610 6 .Sample 1:InputOutput42 12 23 51 120100Explanation:Test case 11 : There are 22 possible special points (0.5,0.5)(0.5,0.5) and (1.5,0.5)(1.5,0.5). In both cases, the first player can select the line 𝑥=1x=1 on his first move, and then the second player is left with no moves. Thus, the first player wins for both the special points.Test case 22 : There are 44 possible special points, all of them end up losing for the first player.

Today, Cat and Fox found an array a𝑎 consisting of n𝑛 non-negative integers.Define the loneliness of a𝑎 as the smallest positive integer k𝑘 (1≤k≤n1≤𝑘≤𝑛) such that for any two positive integers i𝑖 and j𝑗 (1≤i,j≤n−k+11≤𝑖,𝑗≤𝑛−𝑘+1), the following holds:ai|ai+1|…|ai+k−1=aj|aj+1|…|aj+k−1,𝑎𝑖|𝑎𝑖+1|…|𝑎𝑖+𝑘−1=𝑎𝑗|𝑎𝑗+1|…|𝑎𝑗+𝑘−1,where x|y𝑥|𝑦 denotes the bitwise OR of x𝑥 and y𝑦. In other words, for every k𝑘 consecutive elements, their bitwise OR should be the same. Note that the loneliness of a𝑎 is well-defined, because for k=n𝑘=𝑛 the condition is satisfied.Cat and Fox want to know how lonely the array a𝑎 is. Help them calculate the loneliness of the found array.InputEach test consists of multiple test cases. The first line contains a single integer t𝑡 (1≤t≤1041≤𝑡≤104) — the number of test cases. The description of the test cases follows.The first line of each test case contains one integer n𝑛 (1≤n≤1051≤𝑛≤105) — the length of the array a𝑎.The second line of each test case contains n𝑛 integers a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛 (0≤ai<2200≤𝑎𝑖<220) — the elements of the array.It is guaranteed that the sum of n𝑛 over all test cases doesn't exceed 105105.OutputFor each test case, print one integer  — the loneliness of the given array.ExampleinputCopy71032 2 231 0 253 0 1 4 252 0 4 0 270 0 0 0 1 2 480 1 3 2 2 1 0 3outputCopy1134473

A variation of the two player game Nim starts with a single stack of 6 tokens. At eachmove a player divides it into two non-empty stacks. A player who cannot move loses thegame. Min plays first.i. Draw the complete search tree for this game.[6 Marks]ii. The utility function assigns a value 0 to a terminal state if Min wins the game and 1 ifMax wins the game.Apply the MinMax algorithm to the search tree to assign utility values to all states in thesearch tree.[4 Marks]iii. If both Min and Max play a perfect game (always makes correct moves), who will win?Explain your answer and show the winning path(s) for Max or Min.[2 Marks]

You are given an array of positive integers nums.Alice and Bob are playing a game. In the game, Alice can choose either all single-digit numbers or all double-digit numbers from nums, and the rest of the numbers are given to Bob. Alice wins if the sum of her numbers is strictly greater than the sum of Bob's numbers.Return true if Alice can win this game, otherwise, return false. Example 1:Input: nums = [1,2,3,4,10]Output: falseExplanation:Alice cannot win by choosing either single-digit or double-digit numbers.Example 2:Input: nums = [1,2,3,4,5,14]Output: trueExplanation:Alice can win by choosing single-digit numbers which have a sum equal to 15.Example 3:Input: nums = [5,5,5,25]Output: trueExplanation:Alice can win by choosing double-digit numbers which have a sum equal to 25