---
title: Eggs
---

You have $n$ eggs which you can drop from a building with $k$ floors. The eggs always survive falling from some unknown floor $h$ or lower. Any higher than that and they break.

Can you determine $h$ by dropping some of the eggs as few times as possible? An egg that survives the fall can be dropped again.

# Interaction

This is an interactive problem. Start by reading two integers $n$ and $k$: the number of eggs available and the height of the building.

To drop an egg, print "`?` $x$", where $x$ is the floor you wish to drop the egg from $(1 \le x \le k)$. The grader responds with "`Intact`" if the egg did not break or "`Broken`" if it broke and cannot be used again.

Once you have determined the answer, print "`!` $h$", where $h$ is the highest floor that the eggs can be dropped from without breaking.

A testing script can be downloaded [here](files/eggs-test.py). The beginning of the script contains instructions on how to use it.

# Constraints

- $1 \le n \le 20$
- $1 \le h \le k \le 10^5$

# Example interaction

```
2 5
? 2
Intact
? 4
Broken
? 3
Intact
! 3
```

# Scoring

For a given number of eggs $n$ and the highest point $k$, we say that the _optimal strategy_ drops eggs at most $d$ times regardless of $h$. If you drop eggs more than $d$ times, the verdict is WRONG ANSWER.

| Subtask | Constraints | Points    |
| :-----: | ----------- | :-------: |
| 1       | $n=1$       | [score=1] |
| 2       | $n=2$       | [score=2] |
| 3       | $n=20$      | [score=3] |
| 4       | $k \le 50$  | [score=4] |
| 5       | $k \le 500$ | [score=5] |
| 6       | No additional constraints | [score=6] |
