1

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[10005],b[10005],c[10005];
int n,m;
priority_queue<int>q;
int f(int x,int i)
{
	return a[i]*x*x+b[i]*x+c[i];
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>c[i];
	}
	for(int i=1;i<=n;i++){
		int x = -b[i]/(2*a[i]);
		for(int j=x;j>=1;j--){
			if(q.size()<m){
				q.push(f(j,i));
			}
			else{
				if(f(j,i)<q.top()){
					q.pop();
					q.push(f(j,i));
				}
				else{
					break;
				}
			}
		}
		for(int j=max(x,1);;j++){
			if(q.size()<m){
				q.push(f(j,i));
			}
			else{
				if(f(j,i)<q.top()){
					q.pop();
					q.push(f(j,i));
				}
				else break;
			}
		}
	}
	vector<int>ans;
	while(!q.empty()){
		ans.push_back(q.top());
		q.pop();
	}
	for(int i=ans.size()-1;i>=0;i--){
		cout<<ans[i]<<' ';
	}
	return 0;
} 

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
	int id,arrtime,time,level;
	friend bool operator < (node a,node b){
		if(a.level!=b.level)return a.level<b.level;
		else return a.arrtime>b.arrtime;
	}
}a[1500005];
int book[1500005];
signed main()
{
	int cnt=0,id,arrtime,time,level;
	while(cin>>id>>arrtime>>time>>level){
		a[++cnt] = {id,arrtime,time,level};
	}
	int now = 0,st=0;//lst任务开始的时间，lst任务结束的时间
	node lst={0,0,0,0};
	priority_queue<node>q;
	for(int i=1;i<=cnt;i++){
		if(a[i].arrtime>=now){
			if(lst.id!=0)cout<<lst.id<<" "<<now<<endl;
			if(q.empty()){
				lst = a[i];
				now = a[i].arrtime+a[i].time;
				st = a[i].arrtime;
				continue;
			}
			lst = q.top();
			q.pop();
			st = now;
			now = st+lst.time-book[lst.id];
			i--;
		}
		else{
			if(a[i].level>lst.level){
				q.push(lst);
				book[lst.id]+=a[i].arrtime-st;
				lst = a[i];
				now = a[i].arrtime+a[i].time;
				st = a[i].arrtime;
			}
			else{
				q.push(a[i]);
			}
		}
	}
	cout<<lst.id<<" "<<now<<endl;
	while(!q.empty()){
		cout<<q.top().id<<" "<<now+q.top().time-book[q.top().id]<<endl;
		now += q.top().time-book[q.top().id];
		q.pop();
	}
	return 0;
}