#include #include #include #include #include #include #include #define div_ceil(x,y) (((x)+(y)-1)/(y)) using namespace std; struct segment_t { int head; // (inclusive) int tail; // (inclusive) int capacity; int _min; int _max; public: segment_t(int head, int tail, int _min, int _max) : head(head), tail(tail), _min(_min), _max(_max) { capacity = (_max - _min) * (tail - head + 1); } }; class product_t { private: string name; map _dic; // name -> identifier vector _con; // constraint vector _max; vector _min; public: product_t(void) { } public: product_t(string name, int n) : name(name) { _con = vector(n + 2, 1); _max = vector(n + 2, 0); _min = vector(n + 2, 0); _con[0] = 100; } public: void add_ingredient(string name, int perc = -1) { if(perc != 0) { int id = _dic.size() + 1; _dic.insert(make_pair(name, id)); _con[id] = perc; } } public: string get_name(void) const { return name; } public: int get_max(string name) { if(_dic.find(name) == _dic.end()) return 0; return _max[_dic[name]]; } int get_min(string name) { if(_dic.find(name) == _dic.end()) return 0; return _min[_dic[name]]; } public: void solve(void) { vector segs; int n = _dic.size() + 2; int m = 100; int k = 0; int adj_max = -201; int adj_min = +201; for(int i = 0; i < n; i++) { if(_con[i] > 0) { if(k < i) segs.push_back(segment_t(k, i - 1, _con[i], m)); _max[i] = _con[i]; _min[i] = _con[i]; adj_max += m * (i - k) + _con[i]; m = _con[i]; adj_min -= m * (i - k) + _con[i]; k = i + 1; } } for(int i = 0; i < segs.size(); i++) { int rmax = adj_max; int rmin = adj_min; for(int j = 0; j < segs.size(); j++) { if(i != j) { rmax -= segs[j].capacity; rmin -= segs[j].capacity; } } segment_t &s = segs[i]; for(int j = s.head; j <= s.tail; j++) { int rmaxj = rmax - (s.tail - j) * (s._max - s._min); _max[j] = s._max - div_ceil(max(rmaxj, 0), j - s.head + 1); int rminj = rmin - (j - s.head) * (s._max - s._min); _min[j] = s._min + div_ceil(max(rminj, 0), s.tail - j + 1); } } } }; int main(void) { ifstream cin("declaration.in"); int np, nq; while(cin >> np, np) { vector p(np); for(int i = 0; i < np; i++) { string pname; cin >> pname; int n; cin >> n; p[i] = product_t(pname, n); string dmy; getline(cin, dmy); for(int j = 0; j < n; j++) { string line; getline(cin, line); istringstream iss(line); string name; iss >> name; int perc; iss >> perc; if(!iss) perc = -1; p[i].add_ingredient(name, perc); } p[i].solve(); } cin >> nq; for(int i = 0; i < nq; i++) { string verb, name; cin >> verb >> name; if(verb == "most") { string s = ""; int t = 0; for(int i = 0; i < np; i++) { t = max(t, p[i].get_min(name)); } for(int i = 0; i < np; i++) { if(p[i].get_max(name) >= t) { cout << s << p[i].get_name(); s = " "; } } } if(verb == "least") { string s = ""; int t = 100; for(int i = 0; i < np; i++) { t = min(t, p[i].get_max(name)); } for(int i = 0; i < np; i++) { if(p[i].get_min(name) <= t) { cout << s << p[i].get_name(); s = " "; } } } cout << endl; } } }