There is a bus stop near the university. The lessons are over, and n students come to the stop. The i-th student will appear at the bus stop at time ti (all ti's are distinct).

We shall assume that the stop is located on the coordinate axis Ox, at point x = 0, and the bus goes along the ray Ox, that is, towards the positive direction of the coordinate axis, and back. The i-th student needs to get to the point with coordinate xi (xi > 0).

The bus moves by the following algorithm. Initially it is at point 0. The students consistently come to the stop and get on it. The bus has a seating capacity which is equal to m passengers. At the moment when m students get on the bus, it starts moving in the positive direction of the coordinate axis. Also it starts moving when the last (n-th) student gets on the bus. The bus is moving at a speed of 1 unit of distance per 1 unit of time, i.e. it covers distance y in time y.

Every time the bus passes the point at which at least one student needs to get off, it stops and these students get off the bus. The students need 1 + [k / 2] units of time to get off the bus, where k is the number of students who leave at this point. Expression [k / 2] denotes rounded down k / 2. As soon as the last student leaves the bus, the bus turns around and goes back to the point x = 0. It doesn't make any stops until it reaches the point. At the given point the bus fills with students once more, and everything is repeated.

If students come to the stop when there's no bus, they form a line (queue) and get on the bus in the order in which they came. Any number of students get on the bus in negligible time, you should assume that it doesn't take any time. Any other actions also take no time. The bus has no other passengers apart from the students.

Write a program that will determine for each student the time when he got off the bus. The moment a student got off the bus is the moment the bus stopped at the student's destination stop (despite the fact that the group of students need some time to get off).

Input

The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 105) — the number of students and the number of passengers the bus can transport, correspondingly. Next n lines contain descriptions of the students, one per line. Each line contains a pair of integers ti, xi (1 ≤ ti ≤ 105, 1 ≤ xi ≤ 104). The lines are given in the order of strict increasing of ti. Values of xi can coincide.

Output

Print n numbers w1, w2, ..., wn, wi — the moment of time when the i-th student got off the bus. Print the numbers on one line and separate them with single spaces.

Examples

Input

1 10
3 5


Output

8


Input

2 1
3 5
4 5


Output

8 19


Input

5 4
3 5
4 5
5 5
6 5
7 1


Output

11 11 11 11 20


Input

20 4
28 13
31 13
35 6
36 4
52 6
53 4
83 2
84 4
87 1
93 6
108 4
113 6
116 1
125 2
130 2
136 13
162 2
166 4
184 1
192 2


Output

51 51 43 40 93 89 86 89 114 121 118 121 137 139 139 152 195 199 193 195

Note

In the first sample the bus waits for the first student for 3 units of time and drives him to his destination in additional 5 units of time. So the student leaves the bus at the moment of time 3 + 5 = 8.

In the second sample the capacity of the bus equals 1, that's why it will drive the first student alone. This student is the same as the student from the first sample. So the bus arrives to his destination at the moment of time 8, spends 1 + [1 / 2] = 1 units of time on getting him off, and returns back to 0 in additional 5 units of time. That is, the bus returns to the bus stop at the moment of time 14. By this moment the second student has already came to the bus stop. So he immediately gets in the bus, and is driven to his destination in additional 5 units of time. He gets there at the moment 14 + 5 = 19. 

In the third sample the bus waits for the fourth student for 6 units of time, then drives for 5 units of time, then gets the passengers off for 1 + [4 / 2] = 3 units of time, then returns for 5 units of time, and then drives the fifth student for 1 unit of time.
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Ivan Pryvalov (ivan.pryvalov@gmail.com)
 */
public class KROK_Q_C implements Runnable{
	
	static class Passenger{
		int i;
		int arrivalTime;
		int target;
		
		int targetReachedTime = -1;
	}
	
	static class Bus{ 
		int capacity;
		int position = 0;
		List<Passenger> passengers = new ArrayList<Passenger>();

		int offset = 0;
		
		public boolean hasMoreSpace(){
			return passengers.size()-offset < capacity;
		}
		
		public boolean isEmpty(){
			return passengers.size()-offset <= 0;
		}
		
		private Passenger fetchCurrent(){
			Passenger res = passengers.get(offset);
			offset++;
			return res;
		}
		
		private Passenger tryCurrent(){
			return passengers.get(offset);
		}
		
		//passengers should be sorted by target position
		public List<Passenger> fetchNextStop(){
			List<Passenger> list = new LinkedList<Passenger>();
			Passenger firstPass = fetchCurrent();
			list.add(firstPass);
			int nextStopPosition = firstPass.target;
			while(!isEmpty() && tryCurrent().target==nextStopPosition){
				list.add(fetchCurrent());				
			}
			return list;
		}
	}
	
	private void solve() throws IOException {
		int n = scanner.nextInt();//10^5 - number of students
		int m = scanner.nextInt();//10^5 - count places
		Passenger[] p = new Passenger[n];
		for (int i = 0; i < n; i++) {
			Passenger pas = new Passenger();
			pas.i = i;
			pas.arrivalTime = scanner.nextInt();//10^5
			pas.target = scanner.nextInt();//10^4	
			p[i] = pas;
		}
		
		Arrays.sort(p, new Comparator<Passenger>() {
			@Override
			public int compare(Passenger o1, Passenger o2) {
				return o1.arrivalTime-o2.arrivalTime;
			}
		});
		
		Queue<Passenger> queue = new LinkedList<Passenger>();
		for (int i = 0; i < p.length; i++) {
			queue.add(p[i]);
		}
		
		Bus bus = new Bus();
		bus.capacity = m;
		bus.position = 0;
		
		
		Comparator<Passenger> comparatorByPosistion = new Comparator<Passenger>() {
			@Override
			public int compare(Passenger o1, Passenger o2) {
				return o1.target - o2.target;
			}
		};
		int time = 0;		
		while(!queue.isEmpty()){
			while(bus.hasMoreSpace() && !queue.isEmpty()){
				Passenger nextPass = queue.remove();
				bus.passengers.add(nextPass);
				time = Math.max(time, nextPass.arrivalTime);
			}
			Collections.sort(bus.passengers, comparatorByPosistion);
			
			//start moving
			while(!bus.isEmpty()){			
				List<Passenger> listPas = bus.fetchNextStop();
				int nextStopPos = listPas.get(0).target;
				int stopDuration = 1+listPas.size()/2;
				
				time += nextStopPos - bus.position;
				bus.position = nextStopPos;
				for (Passenger pas : listPas) {
					pas.targetReachedTime = time;
				}			
				
				time += stopDuration;
			}
			
			//going back
			time += bus.position;
			bus.position = 0;	
			bus.offset = 0;
			bus.passengers.clear();
		}
		
		Arrays.sort(p, new Comparator<Passenger>() {

			@Override
			public int compare(Passenger o1, Passenger o2) {
				return o1.i - o2.i;
			}
		});
		
		for(int i=0; i<p.length-1; i++){
			out.print(p[i].targetReachedTime + " ");
		}
		out.println(p[p.length-1].targetReachedTime);	
		
	}

	/////////////////////////////////////////////////
	final int BUF_SIZE = 1024 * 1024 * 8;//important to read long-string tokens properly
	final int INPUT_BUFFER_SIZE = 1024 * 1024 * 8 ;
	final int BUF_SIZE_INPUT = 1024;
	
	final int BUF_SIZE_OUT = 1024;
	
	boolean inputFromFile = false;
	String filenamePrefix = "A-small-attempt0";
	String inSuffix = ".in";
	String outSuffix = ".out";
	
	//InputStream bis;
	//OutputStream bos;
	PrintStream out;
	ByteScanner scanner;
	ByteWriter writer;
	
	@Override
	public void run() {
		try{
			InputStream bis = null;
			OutputStream bos = null;
			//PrintStream out = null;
			if (inputFromFile){
				File baseFile = new File(getClass().getResource("/").getFile());
				bis = new BufferedInputStream(
						new FileInputStream(new File(
								baseFile, filenamePrefix+inSuffix)),
								INPUT_BUFFER_SIZE);
				bos = new BufferedOutputStream(
						new FileOutputStream(
								new File(baseFile, filenamePrefix+outSuffix)));
				out = new PrintStream(bos);
			}else{
				bis = new BufferedInputStream(System.in, INPUT_BUFFER_SIZE);
				bos = new BufferedOutputStream(System.out);
				out = new PrintStream(bos);
			}
			scanner = new ByteScanner(bis, BUF_SIZE_INPUT, BUF_SIZE);
			writer = new ByteWriter(bos, BUF_SIZE_OUT);
			
			solve();
			out.flush();
		}catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}
	
	public interface Constants{
		final static byte ZERO = '0';//48 or 0x30
		final static byte NINE = '9';
		final static byte SPACEBAR = ' '; //32 or 0x20
		final static byte MINUS = '-'; //45 or 0x2d	
		
		final static char FLOAT_POINT = '.';
	}
	
	public static class EofException extends IOException{
	}
	
	public static class ByteWriter implements Constants {
		
		int bufSize = 1024;
		byte[] byteBuf = new byte[bufSize];
		OutputStream os;
		
		public ByteWriter(OutputStream os, int bufSize){
			this.os = os;
			this.bufSize = bufSize;
		}
		
		public void writeInt(int num) throws IOException{
	         int byteWriteOffset = byteBuf.length;
	         if (num==0){
	        	 byteBuf[--byteWriteOffset] = ZERO;
	         }else{
	        	 int numAbs = Math.abs(num);
	        	 while (numAbs>0){
	        		 byteBuf[--byteWriteOffset] = (byte)((numAbs % 10) + ZERO);
	        		 numAbs /= 10;
	        	 }
	        	 if (num<0)
	        		 byteBuf[--byteWriteOffset] = MINUS;
	         }
	         os.write(byteBuf, byteWriteOffset, byteBuf.length - byteWriteOffset);
		}
		
		/**
		 * Please ensure ar.length <= byteBuf.length!
		 * 
		 * @param ar
		 * @throws IOException
		 */
		public void writeByteAr(byte[] ar) throws IOException{
			for (int i = 0; i < ar.length; i++) {
				byteBuf[i] = ar[i];
			}
			os.write(byteBuf,0,ar.length);
		}
		
		public void writeSpaceBar() throws IOException{
			byteBuf[0] = SPACEBAR;
			os.write(byteBuf,0,1);
		}
		
	}
	
	public static class ByteScanner implements Constants{
		
		InputStream is;
		
		public ByteScanner(InputStream is, int bufSizeInput, int bufSize){
			this.is = is;
			this.bufSizeInput = bufSizeInput;
			this.bufSize = bufSize;
			
			byteBufInput = new byte[this.bufSizeInput];
			byteBuf = new byte[this.bufSize];
		}
		
		public ByteScanner(byte[] data){
			byteBufInput = data;
			bufSizeInput = data.length;
			bufSize = data.length;
			byteBuf = new byte[bufSize];
			byteRead = data.length;
			bytePos = 0;
		}
		
		private int bufSizeInput;
		private int bufSize;
		
		byte[] byteBufInput;
		byte by=-1;
		int byteRead=-1;
		int bytePos=-1;

		byte[] byteBuf;
		int totalBytes;
		
		boolean eofMet = false;
		
		private byte nextByte() throws IOException{
			
			if (bytePos<0 || bytePos>=byteRead){
				byteRead = is==null? -1: is.read(byteBufInput);
				bytePos=0;
				if (byteRead<0){
					byteBufInput[bytePos]=-1;//!!!
					if (eofMet)
						throw new EofException();
					eofMet = true;
				}
			}
			return byteBufInput[bytePos++];
		}
		
		/**
		 * Returns next meaningful character as a byte.<br>
		 * 
		 * @return
		 * @throws IOException
		 */
		public byte nextChar() throws IOException{
			while ((by=nextByte())<=0x20);
			return by;
		}
		
		/**
		 * Returns next meaningful character OR space as a byte.<br>
		 * 
		 * @return
		 * @throws IOException
		 */
		public byte nextCharOrSpacebar() throws IOException{
			while ((by=nextByte())<0x20);
			return by;
		}
		
	    /**
	     * Reads line.
	     * 
	     * @return
	     * @throws IOException
	     */
	    public String nextLine() throws IOException {
            readToken((byte)0x20);
            return new String(byteBuf,0,totalBytes);
	    }
	    
	    public byte[] nextLineAsArray() throws IOException {
            readToken((byte)0x20);
            byte[] out = new byte[totalBytes];
            System.arraycopy(byteBuf, 0, out, 0, totalBytes);
            return out;
	    }
	    
		
	    /**
	     * Reads token. Spacebar is separator char.
	     * 
	     * @return
	     * @throws IOException
	     */
	    public String nextToken() throws IOException {
            readToken((byte)0x21);
            return new String(byteBuf,0,totalBytes);
	    }
	    
	    /**
	     * Spacebar is included as separator char
	     * 
	     * @throws IOException
	     */
	    private void readToken() throws IOException {	    	
            readToken((byte)0x21);
	    }
	    
	    private void readToken(byte acceptFrom) throws IOException {
            totalBytes = 0;
            while ((by=nextByte())<acceptFrom);
            byteBuf[totalBytes++] = by;
            while ((by=nextByte())>=acceptFrom){
                byteBuf[totalBytes++] = by;
            }
	    }
		
	    public int nextInt() throws IOException{
			readToken();
			int num=0, i=0;
			boolean sign=false;
			if (byteBuf[i]==MINUS){
				sign = true;
				i++;
			}
			for (; i<totalBytes; i++){
				num*=10;
				num+=byteBuf[i]-ZERO;
			}
			return sign?-num:num;
		}
		
		public long nextLong() throws IOException{
			readToken();
			long num=0;
			int i=0;
			boolean sign=false;
			if (byteBuf[i]==MINUS){
				sign = true;
				i++;
			}
			for (; i<totalBytes; i++){
				num*=10;
				num+=byteBuf[i]-ZERO;
			}
			return sign?-num:num;
		}
		
		/*
		//TODO test Unix/Windows formats
		public void toNextLine() throws IOException{
			while ((ch=nextChar())!='\n');
		}
		*/
		
		public double nextDouble() throws IOException{
			readToken();
			char[] token = new char[totalBytes];
			for (int i = 0; i < totalBytes; i++) {
				token[i] = (char)byteBuf[i];
			}
			return Double.parseDouble(new String(token));
		}
	    
	}
	
	public static void main(String[] args) {
		new KROK_Q_C().run();
	}
	
}
