import java.io.PrintStream;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;

/**
 * Solution to Zoning Houses
 * 
 * @author vanb
 */
public class zoning_vanb
{
    private static Scanner sc;
    private static PrintStream ps;
    
    /** Array of X coordinates */
    public long xs[];
    
    /** Array of Y coordinates */
    public long ys[];
    
    /**
     * An interface for a generic node of a Segment Tree
     * 
     * @author vanb
     */
    public interface SegmentTreeValue
    {
        /**
         * Merge two nodes
         * 
         * @param other The other node
         * @return A merged node
         */
        public SegmentTreeValue merge( SegmentTreeValue other );
    }
    
    /**
     * This is the value of a node of the segments tree.
     * It will contain the minimum and maximum X and Y, and the
     * second minimum and maximum X and Y, for every house in its segment.
     * 
     * @author vanb
     *
     */
    public class Limits implements SegmentTreeValue
    {
        /** House numbers for Maximums and minimums */
        public int maxx, maxy, minx, miny;
        
        /** House numbers for Penultimate maxs and mins */
        public int nextmaxx, nextmaxy, nextminx, nextminy;
        
        /**
         * Create a node for House i
         * 
         * @param i INdex of a House
         */
        public Limits( int i )
        {
            // The max and min indices are just i
            maxx = maxy = minx = miny = i;    
            
            // There's only one house, so there are no nexts
            nextmaxx = nextmaxy = -1;
            nextminx = nextminy = -1;    
        }
        
        /**
         * Produce a pretty String for debugging.
         */
        public String toString()
        {
            String pretty = "[ ";
            pretty += "maxx=" + maxx + " (" + xs[maxx] + ") ";
            pretty += "nextmaxx=" + nextmaxx + " (" + (nextmaxx<0?"?":xs[nextmaxx]) + ") ";
            pretty += "minx=" + minx + " (" + xs[minx] + ") ";
            pretty += "nextminx=" + nextminx + " (" + (nextminx<0?"?":xs[nextminx]) + ") ";
            pretty += "maxy=" + maxy + " (" + ys[maxy] + ") ";
            pretty += "nextmaxy=" + nextmaxy + " (" + (nextmaxy<0?"?":ys[nextmaxy]) + ") ";
            pretty += "miny=" + miny + " (" + ys[miny] + ") ";
            pretty += "nextminy=" + nextminy + " (" + (nextminy<0?"?":ys[nextminy]) + ") ";
            pretty += "]";
            
            return pretty;
        }
        
        /** This array will be useful for finding the top 2 */
        private int tops[] = new int[2];
        
        /**
         * Add an element, see if it's in the top 2.
         * 
         * @param i Index of element to add
         * @param v Array of X or Y coordinate values
         * @param max true if seeking maxs, false for mins
         */
        private void addTop( int i, long v[], boolean max )
        {
            if( i>=0 )
            {
                if( tops[0]==-1 || (max && v[i]>v[tops[0]]) || (!max && v[i]<v[tops[0]]) ) 
                {
                    tops[1] = tops[0];
                    tops[0] = i;
                }
                else if( i!=tops[0] && (tops[1]==-1 || (max && v[i]>v[tops[1]]) || (!max && v[i]<v[tops[1]]) )) tops[1] = i;
            }
        }
        
        /**
         * Create a new Limits by merging two other Limits.
         * 
         * @param a A Limits objects
         * @param b Another Limits object
         */
        public Limits( Limits a, Limits b )
        {
            // Get the top 2 Xs
            tops[0] = -1;
            tops[1] = -1;
            addTop( a.maxx, xs, true );
            addTop( b.maxx, xs, true );
            addTop( a.nextmaxx, xs, true );
            addTop( b.nextmaxx, xs, true );
            maxx = tops[0];
            nextmaxx = tops[1];
            
            // Get the bottom 2 Xs
            tops[0] = -1;
            tops[1] = -1;
            addTop( a.minx, xs, false );
            addTop( b.minx, xs, false );
            addTop( a.nextminx, xs, false );
            addTop( b.nextminx, xs, false );
            minx = tops[0];
            nextminx = tops[1];
            
            // Get the top 2 Ys
            tops[0] = -1;
            tops[1] = -1;
            addTop( a.maxy, ys, true );
            addTop( b.maxy, ys, true );
            addTop( a.nextmaxy, ys, true );
            addTop( b.nextmaxy, ys, true );
            maxy = tops[0];
            nextmaxy = tops[1];
            
            // Get the bottom 2 Ys
            tops[0] = -1;
            tops[1] = -1;
            addTop( a.miny, ys, false );
            addTop( b.miny, ys, false );
            addTop( a.nextminy, ys, false );
            addTop( b.nextminy, ys, false );
            miny = tops[0];
            nextminy = tops[1];
        }
        
        /**
         * What side square length do you get 
         * in this segment if you omit house i?
         * 
         * @param i House to omit
         * @return Square side length if you omit i
         */
        public long omit( int i )
        {
            long lox = xs[minx==i ? nextminx : minx];    
            long hix = xs[maxx==i ? nextmaxx : maxx];    
            long loy = ys[miny==i ? nextminy : miny];    
            long hiy = ys[maxy==i ? nextmaxy : maxy];  
            
            return Math.max( hix-lox,  hiy-loy );
        }
        
        @Override
        /**
         * Merge two nodes.
         */
        public SegmentTreeValue merge( SegmentTreeValue other )
        {
            // Just let the constructor do the work
            return new Limits( this, (Limits)other );
        }
        
    }
    
    /**
     * A Segment Tree.
     * 
     * @author vanb
     */
    public class SegmentTree<T extends SegmentTreeValue>
    {
        /** The number of elements */
        public int size;
        
        /** The tree itself */
        public T tree[];
        
        /**
         * Create a Segment Tree for a segment with 'size' elements.
         * 
         * @param size Number of elements
         */
        public SegmentTree( int size )
        {
            this.size = size;
            
            // If there are n elements, then the number of leaves
            // in the Segment Tree could be up to k, where k is the smallest
            // power of 2 greater than or equal to n.
            int k = Integer.highestOneBit( size );
            if( k!=size ) k<<=1;
            
            // A binary tree with k leaves will have k-1 internal nodes.
            // So, we need k+k-1 overall. But, we start at 1, not 0, so
            // we need one more, since there's one (at 0) we won't use.
            tree = (T[]) new SegmentTreeValue[k + k];
            
            // We're use null as a flag that a value hasn't been set here.
            Arrays.fill( tree, null );
        }
        
        /**
         * Put a value over an interval into the Segment tree.
         * This is an internal method.
         * 
         * @param node Index of the current node
         * @param lo Low index of the segment for this node
         * @param hi High index of the segment for this node
         * @param lower Lower bound of the interval of interest
         * @param upper Upper bound of the interval of interest
         * @param value Value to fill in the interval [lower,upper]
         */
        private T put( int node, int lo, int hi, int lower, int upper, T value )
        {
            if( lower<=lo && hi<=upper )
            {
                tree[node] = value;
            }
            else
            {
                // Build left and right subtrees
                int mid = (hi+lo)/2;
                T left=null, right=null;
                if( lower<=mid ) left = put( node+node, lo, mid, lower, upper, value );
                if( upper>mid ) right = put( node+node+1, mid+1, hi, lower, upper, value  );
                
                tree[node] = merge( tree[node], merge( left, right ) );
            }
            
            return tree[node];
        }
        
        /**
         * Put a value over an interval into the Segment tree.
         * This is an outward facing method.
         * 
         * @param lower Lower bound of the interval of interest
         * @param upper Upper bound of the interval of interest
         * @param value Value to fill in the interval [lower,upper]
         */
        public void put( int lower, int upper, T value )
        {
            put( 1, 0, size-1, lower, upper, value );
        }
        
        /**
         * Safely merge two nodes.
         * This uses the objects' merge, but protects against nulls.
         * 
         * @param a A node
         * @param b Another node
         * @return The merging of a and b
         */
        private T merge( T a, T b )
        {
            T result = null;
            if( a!=null && b!=null ) result = (T)a.merge( b );
            else if( a!=null ) result = a;
            else if( b!=null ) result = b;
            
            return result;
        }
        
        /**
         * Get a value from the Segment Tree.
         * This is an internal method.
         * 
         * @param node Index of the current node
         * @param lo Low index of the segment for this node
         * @param hi High index of the segment for this node
         * @param lower Low index of the segment we want to get the value from
         * @param upper High index of the segment we want to get the value from
         * @return
         */
        private T get( int node, int lo, int hi, int lower, int upper )
        {
            T result = null;
            if( node<tree.length )
            {
                if( lower<=lo && hi<=upper )
                {
                    result = tree[node];
                }
                else
                {
                    int mid = (lo+hi)/2;
                    T left = null;
                    T right = null;                
                    if( lower<=mid ) left = get( node+node, lo, mid, lower, upper );
                    if( upper>mid ) right = get( node+node+1, mid+1, hi, lower, upper );
                    
                    result = merge( left, right );
                }
            }
            return result;
        }
        
        /**
         * Get a value from the Segment Tree.
         * This is an outward facing method.
         * 
         * @param lower Low index of the segment we want to get the value from
         * @param upper High index of the segment we want to get the value from
         * @return A node for this segment
         */
        public T get( int lower, int upper )
        {
            return get( 1, 0, size-1, lower, upper );
        }
    }
       
    /**
     * Do it!
     */
    private void doit()
    {     
        int n = sc.nextInt();
        int q = sc.nextInt();
        
        SegmentTree<Limits> limits = new SegmentTree<Limits>(n);
        xs = new long[n];
        ys = new long[n];
        
        // Read in the house locations,
        // put them in the segment tree.
        for( int i=0; i<n; i++ )
        {
            xs[i] = sc.nextLong();
            ys[i] = sc.nextLong();
            limits.put( i, i, new Limits(i) );
        }

        // Perform the queries
        while( q-->0 )
        {
            // We'll translate from 1-based to 0-based
            int a = sc.nextInt()-1;
            int b = sc.nextInt()-1;
            
            // Get the limits of this segment
            Limits l = (Limits)limits.get( a, b );
            
            // Omit each of the maximums, see what we get.
            long side = l.omit( l.maxx );
            side = Math.min( side, l.omit( l.minx ) );
            side = Math.min( side, l.omit( l.maxy ) );
            side = Math.min( side, l.omit( l.miny ) );

            ps.println( side );
        }
    }
        
    /**
     * main
     * 
     * @param args
     * @throws Exception
     */
    public static void main( String[] args ) throws Exception
    {
        sc = new Scanner( System.in );
        ps = System.out;
        
        new zoning_vanb().doit();
    }

}