Consider the two cases for understanding basic pattern in this problem.The first case is that chef has 5 moves and have N = 10 and k = 10 which means he has 15 boxes in front of him and 10 boxes will be added after every choice now chef is making moves. For describing the chefs move I will use 0 if he chooses any box and 1 if he is removing x*k boxes where x*k<N.the optimal string is 1010101010 to maximize the probability because if he chooses any other move pattern he will end up increasing the number of boxes or the denominator so much that the probability will decrease drastically.So now you know he will always choose the box after removing the boxes whenever he can. Now if you will try to compute it like explained above you will see the answer will be expression of GP sum. (excluding the first in some cases where N<k in start and last move in some cases where he cannot remove boxes so he will choose from N+k boxes) We can calculate the gp sum in log m time so the overall time complexity will be O(Tlogm)

Now the next qustion Manhattan Rectangel which is a much easier.

M = 10**9

first I have asked 4 queries from (0,0),(0,M),(M,0),(M,M)

now the 4 equations are

d1 = x1 + y1

d2 = x1 + M - y2

d3 = M - x2 + y1

d4 = M - x2 + M - y2

x1 y1 are the co-ordinate of vertex of rectangle which is nearest to origin and x2 y2 denotes co-ordiantes of rectangle of upper right.

k = 0.5(y1+y2) = (d1-d2+M)0.5

now ask query to (0,k) which will give you the distance x1 because 0.5(y1+y2) is the y cordinate of mid-point of left vertical side of rectangle and it will give nearest distance from (x1,0.5(y1+y2)) and that distance is x1 now put x1 in first 4 equations and you will get other variables