Problem: White Tiger University holds a programming contest every year. The contest starts with a score of 0 for all teams, and points are added according to the answer status. In this contest, rankings will be made in descending order of score. When the total number of teams is N, each team is assigned a number from 1 to N. If the scores are the same, the one with the smaller number will be ranked higher.

White Tiger University is developing a ranking system for watching games to liven up the contest. As a member of the development team, you are responsible for creating the programs that are part of this system.

Create a program that updates the score and reports the number and score of the team in the specified ranking according to the instructions given.



Input

The input is given in the following format.


N C
command1
command2
::
commandC


The number of teams N (2 ≤ N ≤ 100000) and the number of instructions C (1 ≤ C ≤ 100000) are given on the first line. Instructions are given line by line to the following C line. Each instruction is given in the following format.


0 t p


Or


1 m


When the first number is 0, it indicates an update command, and when it is 1, it represents a report command. The update instruction adds the integer score p (1 ≤ p ≤ 109) to the team with the specified number t (1 ≤ t ≤ N). The reporting order reports the number and score of the team with the specified rank m (1 ≤ m ≤ N). However, the reporting order shall appear at least once.

Output

For each report command, the number and score of the team with the specified rank are output on one line separated by blanks.

Examples

Input

3 11
0 2 5
0 1 5
0 3 4
1 1
1 2
1 3
0 3 2
1 1
0 2 1
1 2
1 3


Output

1 5
2 5
3 4
3 6
3 6
1 5


Input

5 2
1 1
1 2


Output

1 0
2 0

Solution (in CPP):

Solution:
#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<map>
using namespace std;
typedef long long int llint;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
const int mod=1000000007;
const llint big=1e18+10;
const long double pai=3.141592653589793238462643383279;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
int gcd(int a,int b){if(a%b==0){return b;}else return gcd(b,a%b);}//a>b
template <class T>
class VEST{
public:
	static VEST *nuve;
	static VEST<T>* warnwarn;
	T val;int size;
	VEST *left,*right;
	VEST(void){size=0;left=nuve;right=nuve;}
	//VEST(VEST *nup){nuve=nup;VEST();}
	~VEST(){if(left!=nuve){delete left;} if(right!=nuve){delete right;}}
	void make_left(void){if(left==nuve&&this!=nuve){this->left=new VEST;}}//null????????????
	void make_right(void){if(right==nuve&&this!=nuve){this->right=new VEST;}}//null????????????
	int nusize(VEST *inptr){return inptr->size;}
	//left???size???????????¨?????????,left???null??§?????§??????
	
};
template<class T>
VEST<T>* VEST<T>::nuve=nullptr;
template<class T>
VEST<T>* VEST<T>::warnwarn=nullptr;
template<class T>
T& youso(VEST<T>* me,int bas){//?????§??????
	if(me->left->size==bas){return me->val;}
	if(me->left->size>bas){return youso(me->left,bas);}
	return youso(me->right,bas- me->left->size -1);
}
template<class T>
void turn_to_right(VEST<T>*& me){
	//ve????????¨?????¨?????????????????????????????§????????§??????(???????????????)
	//???????????¢???????????????
	//??????????????????????????????????????????????????????????????§??????????????¢??°??§??????
	//me????????¨????????¨????????¢????????????me???????????????
	VEST<T> *lr,*l;
	l=me->left;
	lr=l->right;
	l->size=me->size;
	me->size=lr->size+me->right->size+1;
	me->left=lr;
	l->right=me;
	me=l;
}
template<class T>
void turn_to_left(VEST<T>*& me){
	//ve????????¨?????¨?????????????????????????????§????????§??????(???????????????)
	//???????????¢???????????????
	//??????????????????????????????????????????????????????????????§??????????????¢??°??§??????
	//me????????¨????????¨????????¢????????????me???????????????
	VEST<T> *rl,*r;
	r=me->right;
	rl=r->left;
	r->size=me->size;
	me->size=rl->size+me->left->size+1;
	me->right=rl;
	r->left=me;
	me=r;
}
const int turn_num=5;
template<class T>
void heikou_do(VEST<T>*& me){
	//ve???????????????????????°???
	//??????????????????????????????????????????????????????????????§??????????????¢??°??§??????
	//me????????¨????????¨????????¢????????????me???????????????
	if(me->size<turn_num){return ;}
	if(me->left->left->size > me->right->size+turn_num){turn_to_right(me);}
	else if(me->right->right->size > me->left->size+turn_num){turn_to_left(me);}
	else if(me->right->left->size > me->left->size+turn_num){turn_to_right(me->right);turn_to_left(me);}
	else if(me->left->right->size > me->right->size+turn_num){turn_to_left(me->left);turn_to_right(me);}
}
template<class T>
void Insert(VEST<T>*& me,int bas,T inp){
	//a,b,c 1???x???ins-> a,x,b,c
	heikou_do(me);me->size++;
	if(me->size==1){me->val=inp;}//???????????????
	else if(bas<=me->left->size){me->make_left();Insert(me->left,bas,inp);}
	else{me->make_right();Insert(me->right,(bas-me->left->size)-1,inp);}
	
}
template<class T>
void Erase(VEST<T>*&me,int bas){
	me->size--;
	if(me->left->size==bas){Erase_do(me);}
	else if(me->left->size>bas){Erase(me->left,bas);}
	else{Erase(me->right,bas- me->left->size -1);}
}
template<class T>
void Erase_do(VEST<T>*&me){
	if(me->size==0){auto it=me;me=me->nuve;delete it;}
	else if(me->right->size==0){auto it=me->left;me->left=me->nuve;auto iti=me;me=it;delete iti;}
	else{
		auto sw=Erase_left_find(me->right);//????????¨????????????
		me->val=sw->val;//???????§???????????????????move
		delete sw;
	}
}
template<class T>
VEST<T>*& Erase_left_find(VEST<T>*&me){
	//right->left->left...
	me->size--;//?????????????????§
	if(me->left->size==0){me->warnwarn=me;me=me->right;me->warnwarn->right=me->warnwarn->nuve;return me->warnwarn;}
	return Erase_left_find(me->left);
}
template<class T>
int Lower_bound(VEST<T>* me,const T& ti,int kasan=0){
	//ti??\????????????????°?????????°????????????
	//????????¨?????????????????????????????´?????????
	//kasan??§?????????????????¨????????????????????????????°???????????????????
	if(me->size==0){return kasan;}//nuve
	if(me->val<ti){
		kasan+=me->left->size+1;
		return Lower_bound(me->right,ti,kasan);
	}else{return Lower_bound(me->left,ti,kasan);}
}
template <class T>
class Vest{
public:
	VEST<T>* cont;//contents
	VEST<T> nuve;//null of vest
	int size(void){return cont->size;};
	Vest(){
		nuve.size=0;
		nuve.left=&nuve;
		nuve.right=&nuve;
		VEST<T>::nuve=&(this->nuve);
		cont=new VEST<T>;
	}
	void insert(int bas,T inp){Insert(cont,bas,inp);}//not this-> but global
	void erase(int bas){Erase(cont,bas);}
	int lower_bound(const T ti){return Lower_bound(cont,ti);}
	T& operator[](int bas){return youso(cont,bas);}
};

int main(void){
	int n,i,q;cin>>n>>q;
	Vest<pair<llint,int>>hyo;
	vector<llint> pot(n);
	llint ans=0;
	for(i=0;i<n;i++){hyo.ins(0,mp((llint)0,-i));}
	for(i=0;i<q;i++){
		int qu;cin>>qu;
		if(qu==0){
			int t;llint p;
			cin>>t>>p;t--;
			hyo.erase(hyo.lower_bound(mp(pot[t],-t)));
			pot[t]+=p;
			hyo.insert(hyo.lower_bound(mp(pot[t],-t)),mp(pot[t],-t));
		}else{
			llint m;cin>>m;
			cout<<(-hyo[n-m].sec)+1<<" "<<hyo[n-m].fir<<endl;
		}
	}
	return 0;
}