The key point of this problem is that there are (overwhelmingly) more genuine coins than counterfeit coins.

Here, the following holds:

Since there are \(10\) counterfeit coins, any group of \(11\) or more coins of the same type must be genuine.

With this observation, several different solutions are possible; we will describe one of them here.

Consider dividing the \(1000\) coins into groups of \(11\). Then, there will be \(90\) groups of \(11\) coins and a remainder of \(10\) coins.

Among these \(90\) groups of \(11\) coins, at most \(10\) groups may contain counterfeit coins, so we can obtain at least \(80\) groups of \(11\) coins that are all of the same type.

Also, we need \(10\) inspections to divide a group of \(11\) coins into two types (without knowing which is genuine).

From these, the following solution can be established.

• First, use \(900\) inspections to divide all the \(11\)-coin groups into (at most) two types.
• Next, exclude the coins that have been identified as genuine (the coins in which all \(11\) coins are of the same type). Furthermore, record one coin number \(x\) that has been identified as genuine (such a coin always exists).
• At this point, we have up to \(20\) groups of coins whose type is undetermined and the \(10\) leftover coins from the \(11\)-coin grouping. By using up to an additional \(30\) inspections to determine whether each of these coins is of the same type as \(x\), we can identify all counterfeit coins.

This solution can identify all counterfeit coins using a maximum of \(930\) inspections.

Sample Implementation (C++):

#include<bits/stdc++.h>

using namespace std;

int ask(int x,int y){
  cout << "? " << x << " " << y << "\n";
  fflush(stdout);
  int res;
  cin >> res;
  return res;
}

void ans(vector<int> &a){
  cout << "!";
  for(auto &nx : a){
    cout << " " << nx;
  }cout << "\n";
  fflush(stdout);
}

int main(){
  int n,m,q;
  cin >> n >> m >> q; // dummy input
  int ok;
  vector<vector<int>> unknown;
  for(int i=0;i<90;i++){
    int up=i*11+1;
    vector<int> g1={up},g2={};
    for(int j=i*11+2;j<=i*11+11;j++){
      if(ask(up,j)==0){g1.push_back(j);}
      else{g2.push_back(j);}
    }
    if(g2.empty()){
      ok=up;
    }
    else{
      unknown.push_back(g1);
      unknown.push_back(g2);
    }
  }
  for(int i=991;i<=1000;i++){
    unknown.push_back({i});
  }
  vector<int> res;
  for(auto &nx : unknown){
    if(ask(nx[0],ok)==1){
      for(auto &ny : nx){
        res.push_back(ny);
      }
    }
  }
  ans(res);
  return 0;
}