B"This is the hard version of the problem. You can find the easy version in the Div. 2 contest. Both versions only differ in the number of times you can ask your friend to taste coffee. This is an interactive problem. You're considering moving to another city, where one of your friends already lives. There are n caf xc3 xa9s in this city, where n is a power of two. The i -th caf xc3 xa9 produces a single variety of coffee a_i . As you're a coffee-lover, before deciding to move or not, you want to know the number d of distinct varieties of coffees produced in this city. You don't know the values a_1, ldots, a_n . Fortunately, your friend has a memory of size k , where k is a power of two. Once per day, you can ask him to taste a cup of coffee produced by the caf xc3 xa9 c , and he will tell you if he tasted a similar coffee during the last k days. You can also ask him to take a medication that will reset his memory. He will forget all previous cups of coffee tasted. You can reset his memory at most 30 000 times. More formally, the memory of your friend is a queue S . Doing a query on caf xc3 xa9 c will: Doing a reset request will pop all elements out of S . Your friend can taste at most dfrac{3n^2}{2k} cups of coffee in total. Find the diversity d (number of distinct values in the array a ). Note that asking your friend to reset his memory does not count towards the number of times you ask your friend to taste a cup of coffee. In some test cases the behavior of the interactor is adaptive. It means that the array a may be not fixed before the start of the interaction and may depend on your queries. It is guaranteed that at any moment of the interaction, there is at least one array a consistent with all the answers given so far. The first line contains two integers n and k ( 1 <= k <= n <= 1024 , k and n are powers of two). It is guaranteed that"...