Problem: 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és in this city, where n is a power of two. The i-th café 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, …, 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é 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é c will: 

  * Tell you if a_c is in S; 
  * Add a_c at the back of S; 
  * If |S| > k, pop the front element of S. 



Doing a reset request will pop all elements out of S.

Your friend can taste at most (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.

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 1024, k and n are powers of two).

It is guaranteed that (3n^2)/(2k) ≤ 15\ 000.

Interaction

You begin the interaction by reading n and k.

  * To ask your friend to taste a cup of coffee produced by the café c, in a separate line output

? c

Where c must satisfy 1 ≤ c ≤ n. Don't forget to flush, to get the answer.

In response, you will receive a single letter Y (yes) or N (no), telling you if variety a_c is one of the last k varieties of coffee in his memory.

  * To reset the memory of your friend, in a separate line output the single letter R in upper case. You can do this operation at most 30\ 000 times.
  * When you determine the number d of different coffee varieties, output

! d




In case your query is invalid, you asked more than (3n^2)/(2k) queries of type ? or you asked more than 30\ 000 queries of type R, the program will print the letter E and will finish interaction. You will receive a Wrong Answer verdict. Make sure to exit immediately to avoid getting other verdicts.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++; 
  * System.out.flush() in Java; 
  * flush(output) in Pascal; 
  * stdout.flush() in Python; 
  * see documentation for other languages. 



Hack format

The first line should contain the word fixed

The second line should contain two integers n and k, separated by space (1 ≤ k ≤ n ≤ 1024, k and n are powers of two).

It must hold that (3n^2)/(2k) ≤ 15\ 000.

The third line should contain n integers a_1, a_2, …, a_n, separated by spaces (1 ≤ a_i ≤ n).

Examples

Input


4 2
N
N
Y
N
N
N
N


Output


? 1
? 2
? 3
? 4
R
? 4
? 1
? 2
! 3


Input


8 8
N
N
N
N
Y
Y


Output


? 2
? 6
? 4
? 5
? 2
? 5
! 6

Note

In the first example, the array is a = [1, 4, 1, 3]. The city produces 3 different varieties of coffee (1, 3 and 4).

The successive varieties of coffee tasted by your friend are 1, 4, 1, 3, 3, 1, 4 (bold answers correspond to Y answers). Note that between the two ? 4 asks, there is a reset memory request R, so the answer to the second ? 4 ask is N. Had there been no reset memory request, the answer to the second ? 4 ask is Y.

In the second example, the array is a = [1, 2, 3, 4, 5, 6, 6, 6]. The city produces 6 different varieties of coffee.

The successive varieties of coffee tasted by your friend are 2, 6, 4, 5, 2, 5.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vpdd = vector<pdd>;
using vvpdd = vector<vpdd>;
template <typename T>
void ckmin(T& a, const T& b) {
  a = min(a, b);
}
template <typename T>
void ckmax(T& a, const T& b) {
  a = max(a, b);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace __input {
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
template <class Arg, class... Args>
void re(Arg& first, Args&... rest) {
  re(first);
  re(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < (int((a).size())); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = 0; i < (SZ); i++) re(a[i]);
}
}  // namespace __input
using namespace __input;
namespace __output {
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T, size_t SZ>
void pr(const array<T, SZ>& x);
template <class T>
void pr(const vector<T>& x);
template <class T>
void pr(const deque<T>& x);
template <class T>
void pr(const set<T>& x);
template <class T1, class T2>
void pr(const map<T1, T2>& x);
template <class T>
void pr(const T& x) {
  cout << x;
}
template <class Arg, class... Args>
void pr(const Arg& first, const Args&... rest) {
  pr(first);
  pr(rest...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T, bool pretty = true>
void prContain(const T& x) {
  if (pretty) pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? pretty ? ", " : " " : "", a), fst = 0;
  if (pretty) pr("}");
}
template <class T>
void pc(const T& x) {
  prContain<T, false>(x);
  pr("\n");
}
template <class T, size_t SZ>
void pr(const array<T, SZ>& x) {
  prContain(x);
}
template <class T>
void pr(const vector<T>& x) {
  prContain(x);
}
template <class T>
void pr(const deque<T>& x) {
  prContain(x);
}
template <class T>
void pr(const set<T>& x) {
  prContain(x);
}
template <class T1, class T2>
void pr(const map<T1, T2>& x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg& first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg& first, const Args&... rest) {
  pr(first, " ");
  ps(rest...);
}
}  // namespace __output
using namespace __output;
namespace __algorithm {
template <typename T>
void dedup(vector<T>& v) {
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
}
template <typename T>
typename vector<T>::iterator find(vector<T>& v, const T& x) {
  auto it = lower_bound((v).begin(), (v).end(), x);
  return it != v.end() && *it == x ? it : v.end();
}
template <typename T>
size_t index(vector<T>& v, const T& x) {
  auto it = find(v, x);
  assert(it != v.end() && *it == x);
  return it - v.begin();
}
template <typename C, typename T, typename OP>
vector<T> prefixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = 0; i < (int((v).size())); i++) r[i + 1] = op(r[i], v[i]);
  return r;
}
template <typename C, typename T, typename OP>
vector<T> suffixes(const C& v, T id, OP op) {
  vector<T> r(int((v).size()) + 1, id);
  for (int i = (int((v).size())) - 1; i >= 0; i--) r[i] = op(v[i], r[i + 1]);
  return r;
}
}  // namespace __algorithm
using namespace __algorithm;
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
struct monostate {
  friend istream& operator>>(istream& is, const monostate& ms) { return is; }
  friend ostream& operator<<(ostream& os, const monostate& ms) { return os; }
  friend monostate operator+(const monostate& a, const monostate& b) {
    return a;
  }
} ms;
#pragma GCC diagnostic pop
namespace __io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(15);
  if (int((second).size())) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace __io
using namespace __io;
bool taste(int loc) {
  cout << "? " << loc + 1 << endl;
  char r;
  re(r);
  if (r == 'E') assert(0);
  return r != 'Y';
}
int main() {
  setIO();
  int N, K;
  re(N, K);
  int SZ = max(K / 2, 1);
  int M = N / SZ;
  vi ct(N, 1);
  for (int j = (1); j < (M); j++) {
    for (int res = 0; res < (j); res++)
      if (res + j < M) {
        cout << "R" << endl;
        for (int i = res; i < M; i += j) {
          for (int k = 0; k < (SZ); k++) ct[i * SZ + k] &= taste(i * SZ + k);
        }
      }
  }
  cout << "! " << accumulate((ct).begin(), (ct).end(), 0) << endl;
  return 0;
}