http://codeforces.com/problemset/problem/421/C

Nearly each project of the F company has a whole team of developers working on it. They often are in different rooms of the office in different cities and even countries. To keep in touch and track the results of the project, the F company conducts shared online meetings in a Spyke chat.

One day the director of the F company got hold of the records of a part of an online meeting of one successful team. The director watched the record and wanted to talk to the team leader. But how can he tell who the leader is? The director logically supposed that the leader is the person who is present at any conversation during a chat meeting. In other words, if at some moment of time at least one person is present on the meeting, then the leader is present on the meeting.

You are the assistant director. Given the 'user logged on'/'user logged off' messages of the meeting in the chronological order, help the director determine who can be the leader. Note that the director has the record of only a continuous part of the meeting (probably, it's not the whole meeting).

Input

The first line contains integers n and m (1 ≤ n, m ≤ 105) — the number of team participants and the number of messages. Each of the next m lines contains a message in the format:

  • '+ id': the record means that the person with number id (1 ≤ id ≤ n) has logged on to the meeting.
  • '- id': the record means that the person with number id (1 ≤ id ≤ n) has logged off from the meeting.

Assume that all the people of the team are numbered from 1 to n and the messages are given in the chronological order. It is guaranteed that the given sequence is the correct record of a continuous part of the meeting. It is guaranteed that no two log on/log off events occurred simultaneously.

Output

In the first line print integer k (0 ≤ k ≤ n) — how many people can be leaders. In the next line, print k integers in the increasing order — the numbers of the people who can be leaders.

If the data is such that no member of the team can be a leader, print a single number 0.：：

题意：有一个n个人的小组，内部有一名小组长。

一个人是小组长等价于<只要会议中有人在线，他就必须在线>，给出整个会议的一部分连续记录（不一定完整，但一定是连续的），每条记录+表示上线，-表示下线。

求哪些人有可能是小组长。

思路：

首先，在记录中没有出现过的人必定是有可能的，把他放到第一个+和最后一个-就是了。

其次，按照是否有某个人第一次出现在记录中是'-'分两类。

①存在若干人第一次出现在记录中是'-'，那么这些人中只有最后一个人有可能是组长，对于前面的人，由于后面还有人在线而他们就下线了，所以他们不可能是组长。最后一个人（设为p）是不是真的有可能是组长，还要再判断，用set维护当前在线的人的集合（初次'-'的这些人不算），<1>如果当前还有人在线，p就下线，那么p不是组长，<2>或者p当前在下线状态，有别人上线了，也说明p不是组长。

②记录中的所有人第一次出现都是'+'，那么只有第一个人可能是组长，因为第一人在线后面的不在线，所以他们不可能是组长。第一个人究竟是否可能是组长，还要再判断。设第一个人是p，与上面同样的方法，用set维护当前在线的人的集合，<1>如果当前还有人在线，p就下线，那么p不是组长，<2>或者p当前在下线状态，有别人上线了，也说明p不是组长。

就后问题就得到解决了，这样的码农题感觉很复杂，还是太菜了。

#include<bits/stdc++.h>
using namespace std;
#define maxn 100000+1000

int n,m,qt[maxn],qp[maxn];
bool vis[maxn];
vector<int> ago,ans;

void solve1()
{
	set<int> online; 
	int p=qp[ago[ago.size()-1]];
	for(int i=0;i<ago.size();i++)online.insert(qp[ago[i]]);
	for(int i=1;i<=ago[ago.size()-1];i++)
	{
		if(qt[i]==1)online.insert(qp[i]);
		else online.erase(qp[i]);
	}
	int nowp=1;
	for(int i=ago[ago.size()-1];i<=m;i++)
	{
		if(online.size()&&qp[i]==p)return;
		if(qp[i]==p)nowp=(qt[i]==1?1:-1);
		if(nowp==-1&&qp[i]!=p)return;
		if(qp[i]!=p&&qt[i]==1)online.insert(qp[i]);
		if(qp[i]!=p&&qt[i]==-1)online.erase(qp[i]);
	}
	ans.push_back(p);
}

void solve2()
{
	int p=qp[1];
	set<int> online; 
	int nowp=1;
	for(int i=2;i<=m;i++)
	{	
		if(online.size()&&qp[i]==p)return;
		if(qp[i]==p)nowp=(qt[i]==1?1:-1);
		if(nowp==-1&&qp[i]!=p)return;
		if(qp[i]!=p&&qt[i]==1)online.insert(qp[i]);
		if(qp[i]!=p&&qt[i]==-1)online.erase(qp[i]);
		
	}
	ans.push_back(p);
}

int main()
{
	//freopen("input.in","r",stdin);
	cin>>n>>m;
	char str[2];
	for(int i=1;i<=m;i++)
	{
		scanf("%s%d",str,&qp[i]);
		if(str[0]=='+')qt[i]=1; else qt[i]=-1;
		if(!vis[qp[i]]&&qt[i]==-1)ago.push_back(i);
		vis[qp[i]]=1;
	}
	if(ago.size())solve1();
	else solve2();
	for(int i=1;i<=n;i++)if(!vis[i])ans.push_back(i);
	cout<<ans.size()<<endl;
	sort(ans.begin(),ans.end());
	for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";
	return 0;	
}