#include <iostream>
#include <string>
#include <cmath>
#include <unordered_map>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_set>
using namespace std;
// 打印机队列
void demo1()
{
struct Event {
int prio;
int index;
struct CmpBigHeap {
bool operator() (const Event& a, const Event& b) {
if(a.prio != b.prio)
return a.prio < b.prio;
return a.index > b.index;
}
};
};
priority_queue<Event, vector<Event>, Event::CmpBigHeap> pq[5];
int N;
cin >> N;
int inIndex = 0;
for(int i = 0; i < N; ++i) {
string s;
int printer, prio;
cin >> s >> printer;
printer--;
if(s == "IN") {
cin >> prio;
inIndex++;
Event t = {prio, inIndex};
pq[printer].push(t);
}
else if (s == "OUT") {
if(pq[printer].empty())
cout << "NULL" << endl;
else {
cout << pq[printer].top().index << endl;
pq[printer].pop();
}
}
}
}
// 机器人活动区域
int demo2_dfs(vector<vector<int> >& grid, vector<vector<bool> >& visited, int x, int y)
{
int count = 1;
int m = grid.size(); // 总行
int n = grid[0].size(); // 总列
visited[x][y] = true;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
for(int i = 0; i < 4; ++i) {
int newX = x + dx[i];
int newY = y + dy[i];
if(newX < 0 || newX >= m || newY < 0 || newY >= n) {
continue;
}
if( abs(grid[x][y] - grid[newX][newY]) > 1) {
continue;
}
if(visited[newX][newY]) {
continue;
}
count += demo2_dfs(grid, visited, newX, newY);
}
return count;
}
void demo2()
{
int m, n, k;
cin >> m >> n;
vector<vector<int> > grid(m, vector<int>(n, 0));
vector<vector<bool> > visited(m, vector<bool>(n, false));
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
cin >> grid[i][j];
}
}
int count = 1;
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(visited[i][j] == false) {
int ret = demo2_dfs(grid, visited, i, j);
count = max(count, ret);
}
}
}
cout << count << endl;
}
// 敏感字段加密
void demo3()
{
int k;
cin >> k;
string s;
cin >> s;
vector<string> cmdWords;
int i = 0;
int n = s.size();
while(i < n) {
if(s[i] == '_') {
i++;
continue;
}
else if(s[i] == '"') {
int j = i+1;
while( j < n && s[j] != '"') j++;
cmdWords.emplace_back(s.substr(i, j-i+1));
i = j+1;
}
else {
int j = i+1;
while(j < n && s[j] != '_') j++;
cmdWords.emplace_back(s.substr(i, j-i));
i = j;
}
}
if(k >= cmdWords.size()) {
cout << "ERROR" << endl;
return;
}
cmdWords[k] = "******";
for(int i = 0; i < cmdWords.size(); ++i) {
if(i) cout << "_";
cout << cmdWords[i];
}
}
// 数组连续和
void demo4()
{
int N, x;
cin >> N >> x;
vector<int> arr(N);
for(int i = 0; i < N; ++i) {
cin >> arr[i];
}
int sumWin = 0;
vector<vector<int> > res; // 结果集
int left= 0, right=0; // 窗口边界
int count = 0;
for( ; right < arr.size(); ++right) {
sumWin += arr[right];
while(sumWin >= x) {
count += N -right;
sumWin -= arr[left];
left++;
}
}
cout << count;
}
// 挑选宝石
void demo5()
{
int n, x, y; // 总宝石数、可选宝石数、最低属性值
cin >> n >> x >> y;
vector<int> baseVals(n);
for(int i = 0; i < n; ++i) {
cin >> baseVals[i];
}
int ans = 0;
for(int mask = 0; mask < (1<<n); ++mask) {
int cnt = 0;
long long product = 1;
for(int i = 0; i < n; ++i) {
if(mask & (1<<i)) {
cnt++;
product *= baseVals[i];
}
}
if(cnt <= x && product >= y) {
ans++;
}
}
cout << ans << endl;
}
// 整数编码
void demo6()
{
unsigned long long n;
cin >> n;
if(n == 0) {
cout << "00" << endl;
return;
}
while(n >0) {
unsigned char byte = n & 0x7F;
n = n >> 7;
if(n != 0) {
byte |= 0x80;
}
printf("%02X", byte);
}
}
// 最佳信号覆盖
void demo7()
{
struct AP {
int x, y, s;
};
int N, D; // AP数，AP覆盖的最大距离
cin >> N >> D;
vector<AP> aps(N);
int maxX = 0, maxY = 0;
for(int i = 0; i < N; ++i) {
cin >> aps[i].x >> aps[i].y >> aps[i].s;
maxX = max(maxX, aps[i].x);
maxY = max(maxY, aps[i].y);
}
vector<vector<int> > points;
int maxSignal = 0;
int bestx = 0, besty = 0;
for(int x = 0; x <= maxX + D; ++x) {
for(int y = 0; y <= maxY + D; ++y) {
int total = 0;
for(int k = 0; k < N; ++k) {
int d = max(abs(aps[k].x - x), abs(aps[k].y - y));
if(d <= D) {
total += aps[k].s / (1 + d);
}
}
if(total > maxSignal) {
maxSignal = total;
bestx = x;
besty = y;
}
else if(total == maxSignal) {
if(x < bestx || (x == bestx && y < besty)) {
bestx = x;
besty = y;
}
}
}
}
cout << bestx << " " << besty;
}
// 冠亚季军
struct Player {
int id;
long long power;
};
bool win(Player&a, Player& b) { // a > b
if(a.power == b.power) return a.id < b.id;
return a.power > b.power;
}
void demo8()
{
long long n;
vector<Player> players;
int id = 0;
while(cin >> n) {
players.push_back({id++, n});
}
Player no1, no2, no3;
while(1) {
vector<Player> next;
for(int i = 0; i < players.size(); i += 2) {
if(i+1 >= players.size()) {
next.push_back(players[i]);
}
else {
if(win(players[i], players[i+1])) {
next.push_back(players[i]);
}
else {
next.push_back(players[i+1]);
}
}
}
players = next;
if(players.size() == 3) {
if(win(players[0], players[1])) {
no3 = players[1];
if(win(players[0], players[2])) {
no1 = players[0];
no2 = players[2];
}
else {
no1 = players[2];
no2 = players[0];
}
}
else {
no3 = players[0];
if(win(players[1], players[2])) {
no1 = players[1];
no2 = players[2];
}
else {
no1 = players[2];
no2 = players[1];
}
}
break;
}
else if(players.size() == 4) {
Player winner[2];
Player lose[2];
if(win(players[0], players[1])) {
winner[0] = players[0];
lose[0] = players[1];
}
else {
winner[0] = players[1];
lose[0] = players[0];
}
if(win(players[2], players[3])) {
winner[1] = players[2];
lose[1] = players[3];
}
else {
winner[1] = players[3];
lose[1] = players[2];
}
if(win(winner[0], winner[1])) {
no1 = winner[0];
no2 = winner[1];
}
else {
no1 = winner[1];
no2 = winner[0];
}
no3 = win(lose[0], lose[1]) ? lose[0] : lose[1];
break;
}
}
cout << no1.id << " " << no2.id << " " << no3.id << endl;
}
// 补种未成活胡杨树
void demo9()
{
int N, M, K;
cin >> N;
cin >> M;
vector<int> trees(N, 1);
for(int i = 0; i < M; ++i) {
int dead_pos;
cin >> dead_pos;
trees[dead_pos] = 0;
}
cin >> K;
int left = 0;
int dead_count = 0;
int res_max = 0;
for(int right = 0; right < N; ++right) {
if(!trees[right]) {
dead_count++;
}
// if dead_count > K, 不够补活的, 需要left指针右移
while(dead_count > K) {
if(!trees[left]) { // 如果left下标的是死树，dead_count需要-1
dead_count--;
}
left--;
}
// if dead_cout <= K, 完全够补活的，可以计算当前区间长度
res_max = max(res_max, right - left + 1);
}
cout << res_max;
}
// 猜数字
int numYesPosNoCount(int answer, int guess)
{
vector<int> ans = {answer / 1000, answer % 1000 / 100, answer %100 / 10, answer % 10};
vector<int> gue = {guess / 1000, guess % 1000 / 100, guess %100 / 10, guess % 10};
vector<int> used(4, 0);
int count = 0;
for(int i = 0; i < ans.size(); ++i) {
for(int j = 0; j < gue.size(); ++j) {
if(ans[i] == gue[j] && i != j && !used[j]) {
count++;
used[j] = 1;
break;
}
}
}
return count;
}
int numYesPosYesCount(int answer, int guess)
{
int count = 0;
if(answer / 1000 == guess / 1000) count++;
if(answer % 1000 / 100 == guess % 1000 / 100) count++;
if(answer % 100 / 10 == guess % 100 / 10) count++;
if(answer % 10 == guess % 10) count++;
return count;
}
void demo10()
{
int n;
cin >> n;
vector<vector<int> > v(n, vector<int>(3));
vector<int> res;
string s;
int t;
for(int i = 0; i < n; ++i) {
cin >> v[i][0];
cin >> s;
v[i][1] = s[0] - '0';
v[i][2] = s[2] - '0';
}
for(int i = 0; i <= 9999; ++i) {
int flag = 0;
for(int j = 0; j < n; ++j) {
if(numYesPosNoCount(i, v[j][0]) == v[j][2] && numYesPosYesCount(i, v[j][0]) == v[j][1]) {
continue;
}
flag = 1;
break;
}
if(!flag) {
res.push_back(i);
}
}
if(res.size() == 1) {
printf("%04d", res[0]);
}
else {
cout << "NA" << endl;
}
}
// 采购订单
void demo11()
{
struct product {
int id;
int price;
int amount;
};
vector<product> res;
map<int, pair<int, int> > low;
int n;
cin >> n;
for(int i = 0; i < n; ++i) {
int id, amount, price, prStatus;
cin >> id >> amount >> price >> prStatus;
if (prStatus == 0) {
if(price > 100) {
res.push_back({id, price, amount});
}
else {
if(low.count(id)) {
low[id].second += amount;
}
else {
low[id] = {price, amount};
}
}
}
}
for(auto& m: low) {
int id = m.first;
int pri = m.second.first;
int amou = m.second.second;
if(amou >= 100) {
pri = (pri * 9 + 9) / 10;
}
res.push_back({id, pri, amou});
}
sort(res.begin(), res.end(), [](product& a, product& b){
if(a.id != b.id) {
return a.id < b.id;
}
return a.amount > b.amount;
});
for(auto it : res) {
cout << it.id << " "
<< it.amount << " "
<< it.price << endl;
}
}
// 查找单入口区域
int m, n;
int dfs_demo12(vector<vector<char> >& grid, vector<vector<bool> >& visited, int x, int y)
{
}
void demo12()
{
cin >> m >> n;
vector<vector<char> > grid(m, vector<char>(n));
vector<vector<bool> > visited(m, vector<bool>(n, false));
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
cin >> grid[i][j];
}
}
int maxArea = 0;
int sameAreaCount = 0;
int maxAreaX = -1, maxAreaY = -1;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; ++j) {
int boundarOCount = 0;
int area = 0;
int ex = -1, ey = -1;
if(grid[i][j] == 'O' && ! visited[i][j]) {
visited[i][j] = true;
queue<pair<int, int> > q;
q.push({i, j});
while(!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
area++;
if(x == 0 || x == m-1 || y == 0 || y == n-1) {
boundarOCount++;
ex = x;ey = y;
}
for(int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if(nx >= 0 && ny >= 0 && nx < m && ny < n) {
if(grid[nx][ny] == 'O' && ! visited[nx][ny]) {
q.push({nx, ny});
visited[nx][ny] = true;
}
}
}
}
if(boundarOCount == 1) {
if(maxArea < area) {
maxArea = area;
maxAreaX = ex;
maxAreaY = ey;
}
else if(maxArea == area) {
sameAreaCount++;
}
}
}
}
}
if(maxArea == 0) cout << "NULL";
else if(sameAreaCount == 1) {
cout << maxAreaX << " " << maxAreaY << " " << maxArea;
}
else {
cout << maxArea;
}
}
// 查找接口成功率最优时间段
void demo13()
{
int minAverageLost;
cin >> minAverageLost;
vector<int> lost;
int t;
int sum = 0;
while(cin >> t) {
lost.push_back(t);
}
int n = lost.size();
int bestTime = 0;
vector<int> prefixSum(n+1, 0);
for(int i = 1; i <= n; ++i) {
prefixSum[i] = prefixSum[i-1] + lost[i-1];
}
vector<vector<int> > res; // 换成pair<int, int>更好
for(int i = 0; i < n; ++i) {
for(int j = i; j < n; ++j) {
int sum = prefixSum[j+1] - prefixSum[i];
int len = j-i+1;
if( sum <= minAverageLost * len) {
if(bestTime < len) {
bestTime = len;
res.clear();
res.push_back({i, j});
}
else if(bestTime == len) {
res.push_back({i, j});
}
}
}
}
for(int i = 0; i < res.size(); ++i) {
cout << res[i][0] << "-" << res[i][1] << " ";
}
if(res.size() == 0) cout << "NULL";
}
// 敌情监控
void demo14()
{
int n, k, l, t;
cin >> n >> k >> l;
vector<int> soldiers(n);
for(int i = 0; i < n; ++i) {
cin >> soldiers[i];
}
vector<int> prefixSum(n+1, 0);
for(int i = 1; i <= n; ++i) {
prefixSum[i] = prefixSum[i-1] + soldiers[i-1];
}
for(int m = 0; m < l; ++m) {
string cmd;
int ti, tj;
cin >> cmd >> ti >> tj;
if(cmd == "Query") {
int minSum = 0;
for(int left = ti; left <= tj + 1 -k; ++left) {
int sum = prefixSum[left+k-1] - prefixSum[left-1];
minSum = min(minSum, sum);
}
cout << min << endl;
}
else if(cmd == "Add") {
soldiers[ti-1] += tj;
}
else if(cmd == "Sub") {
soldiers[ti-1] -= tj;
}
else {
// input error
}
for(int i = ti; i <= n; ++i) {
prefixSum[i] = prefixSum[i-1] + soldiers[i-1];
}
}
}
// 斗地主之顺子
void demo15()
{
vector<string> cardVal = {"3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A"};
set<string> cards;
string s;
while(cin >> s) {
cards.insert(s);
}
bool found = false;
for(int i = 0; i < cardVal.size(); ++i) {
int j = i;
if(cards.count(cardVal[j])) {
vector<string> temp;
while(j < cardVal.size() && cards.count(cardVal[j])) {
temp.push_back(cardVal[j]);
j++;
}
if(temp.size() >= 5) {
found = true;
for(int k = 0; k < temp.size(); ++k) {
cout << temp[k];
if(k != temp.size() -1) cout << " ";
}
cout << end;
}
}
i = j -1;
}
if(!found) {
cout << "NO";
}
}
// 风险投资计划
void demo16()
{
int m, n, x, y;
cin >> m >> n >> x >> y;
vector<int> prod;
int e, r;
while(cin >> e >> r) {
if(r <= x) {
prod.push_back(e);
}
}
sort(prod.begin(), prod.end(), [](int a, int b){return a> b;}); // 降序
n = prod.size();
int sumE = 0, cost = 0;
#if 1
for(int i = 0; i < n; ++i) {
cost += y ; // 每个产品按最高y投资
if(cost <= m) {sumE += y*prod[i];}
else {
int left = m - (cost - y);
sumE += left * prod[i];
break; // 超出预算
}
}
int max = (sumE % 100) / 10 >= 5
? sumE/100 + 1
: sumE/100;
cout << max << endl;
#else
int money = m;
double profit = 0.0;
for(int i = 0; i < n && money > 0; ++i) {
int invest = min(y, money);
profit += invest * prod[i] / 100.0;
money -= y;
}
cout << (int)(profit + 0.5) << endl;
#endif
}
// 高矮个子排队
void demo17()
{
vector<int> heights;
string s;
while(cin >> s) {
for(int i = 0; i < s.size(); ++i) {
if(s[i] >= '0' && s[i] <= '9') {
continue;
}
cout << "[ ]";
return;
}
heights.push_back(stoi(s));
}
for(int i = 0; i < heights.size() - 1; ++i) {
if(i % 2==0 && heights[i] < heights[i+1]) {
swap(heights[i], heights[i+1]);
}
else if(i%2 == 1 && heights[i] > heights[i+1]) {
swap(heights[i], heights[i+1]);
}
}
for(int i = 0; i < heights.size(); ++i) {
cout << heights[i];
if(i != heights.size()-1) cout << " ";
}
cout << endl;
}
// 构成正方形的数量
void demo18()
{
int n;
vector<pair<int, int> > pos;
set<pair<int, int> > us;
cin >> n;
for(int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
pos.push_back({x, y});
us.insert({x, y});
}
int count = 0;
for(int i = 0; i < pos.size(); ++i) {
int ax = pos[i].first, ay = pos[i].second;
for(int j = i+1; j < pos.size(); ++j) {
int bx = pos[j].first, by = pos[j].second;
int tx = bx - ax;
int ty = by - ay;
// 旋转90°
int dx = ax - ty, dy = ay + tx;// d点是b逆时针旋转90
int cx = bx - ty, cy = by + tx;// c点是a顺时针旋转90
if(us.count({dx, dy}) && us.count({cx, cy})) {
count++;
}
dx = ax + ty, dy = ay - tx; // d点是 b顺时针旋转90
cx = bx + ty, cy = by - tx; // c点是 a逆时针旋转90
if(us.count({dx, dy}) && us.count({cx, cy})) {
count++;
}
}
}
cout << count/4 << endl;
}
// 恢复数字序列
void demo19_1()
{
string s;
int digistLen;
cin >> s >> digistLen;
map<char, int> mp;
for(int i = 0; i < s.size(); ++i) {
mp[s[i]]++;
}
int left = 1;
int right = left + digistLen -1;
while(right <= 1000) {
int windowLeft = left, windowRight = right;
string t("");
for(; windowLeft <= windowRight; ++windowLeft) {
t += to_string(windowLeft);
}
map<char, int> mt;
bool match = true;
for(int i = 0; i < t.size(); ++i) {
mt[t[i]]++;
}
for(auto& [key, value] : mp) {
if(mt[key] != value) {
match = false;
break;
}
}
if(match) {
cout << left;
return;
}
left++;
right++;
}
}
void demo19_2()
{
}
// 精准核算检测
struct Solution20 {
int getCheckPeople(vector<vector<int> >& mat, vector<int>& infected) {
int count = 0;
queue<int> q;
int infectedCount = infected.size();
int totol = mat.size();
vector<bool> visited(totol, false); // 默认所有人都未被检查
for(int i = 0; i < infectedCount; ++i) {
visited[infected[i]] = true;
q.push(infected[i]);
}
while(!q.empty()) {
vector<int> t = mat[q.front()];
q.pop();
for(int j = 0; j < t.size(); ++j) {
// // j号未被访问，且与感染者有接触
if(visited[j] == false && t[j] == 1) {
q.push(j);
visited[j] = true; // 标记为已访问
}
}
}
for(int i = 0; i < totol; ++i) {
if(!visited[i]) count++;
}
return count - infectedCount;
}
};
int main()
{
demo1();
return 0;
}