public:
string findShortestNewSequence(string s) {
  m.clear();

  rep(i, s.size()) {
      stringstream ss;
      REP(j, i, s.size()) {
          string t = s.substr(i, j-i+1);
          if(t.size() >= 10) continue;
          m[t] = true;
      }
  }

  que.push("A");
  que.push("C");
  que.push("G");
  que.push("T");

  string ans = "";
  while(que.size()) {
      string t = que.front();
      que.pop();

      if(!m[t]) {
          ans = t;
          break;
      }

      que.push(t + "A");
      que.push(t + "C");
      que.push(t + "G");
      que.push(t + "T");
  }

  // last check
  return ans;
}