import java.io.*;
import java.util.*;
import java.math.*;

/**
 * Solution to Fantastic Problem
 * 
 * Two numbers are coprime if they share no factors other than one. If two numbers
 * are NOT coprime, that means that they share a factor (>1), so they have to share a prime factor.
 * So, we'll keep track of the prime factors of every number. We'll also keep track of the 
 * index of every occurrence of a prime in the list. For each prime, we'll keep the indices
 * in a balanced AVL search tree, so they're easy to find.
 * 
 * If two numbers share a prime factor, and they're close to each other in Andrew's sequence, 
 * then they'll create a number of size-k intervals that contain non-coprime numbers. For example:
 * 
 * 1 3 7 5 11 15 19 21 23 31 
 * 
 * The 5 and the 15 share 5 as a factor. If k=6, this creates four bad intervals:
 * 
 * 1 3 7 5 11 15
 * 3 7 5 11 15 19
 * 7 5 11 15 19 21
 * 5 11 15 19 21 23
 * 
 * We'll keep track of the indices of the rightmost endpoint of each bad interval.
 * In this case, that would be 5,6,7,8 (assuming the first index is 0), or the interval [5..8].
 * We'll use a segment tree with lazy propagation to keep track of these intervals of interval ends.
 * We'll also keep a parallel tree to keep track of a count of such intervals.
 * 
 * @author vanb
 */
public class fantastic_vanb
{    
    public Scanner sc;
    public PrintStream ps;
    
    /** Length of list, size of interval, number of fixes */
    public int n, k, m;
    
    /** A list of primes */
    public int primes[] = new int[10000];
    
    /** Total number of primes */
    public int np;
    
    /** Andrew's sequence */
    public int sequence[] = new int[100000];
    
    /** Prime breakdown of every number from 1 to 100,000 */
    public int factors[][] = new int[100001][7];
    
    /** The last appearance of each prime */
    public int last[] = new int[10000];
        
    /**
     * Node of a balanced AVL binary tree, and a doubly linked sorted list.
     * 
     * @author vanb
     */
    public class Node
    {
        // Value in the node, height of this subtree
        public int value, height;
        
        // Links to left child, right child and parent,
        // along with previous and next nodes of a linked linear list.
        public Node left, right, parent, prev, next; 
        
        /**
         * Create a new unlinked node.
         * 
         * @param v Value for this node.
         */
        public Node( int v )
        {
            value = v;
            height = 0;
            left = right = parent = prev = next = null;
        }

        /**
         * Height of the left subtree
         * 
         * @return Height of the left subtree
         */
        public int leftheight()
        {
            return left==null ? 0 : left.height;
        }
        
        /**
         * Height of the right subtree 
         * 
         * @return Height of the right subtree
         */
        public int rightheight()
        {
            return right==null ? 0 : right.height;
        }
                   
        /**
         * Recalculate the height of this node
         */
        public void recalc()
        {
            height = 1 + Math.max( leftheight(), rightheight() );
        }
        
        /**
         * Perform an AVL tree rotate left on this node.
         */
        public void rotateleft()
        {
            Node p = parent;
            Node pivot = right;
            Node subtree = pivot.left;
            
            right = subtree;
            if( subtree!=null ) subtree.parent = this;
            
            parent = pivot;
            pivot.left = this;
            
            if( p==null ) root = pivot;   
            else if( p.left == this ) p.left = pivot;
            else p.right = pivot;   

            pivot.parent = p;
            
            recalc();
            pivot.recalc();
            if( p!=null ) p.recalc();
        }
        
        /**
         * Perform an AVL tree rotate right on this node.
         */
        public void rotateright()
        {
            Node p = parent;
            Node pivot = left;
            Node subtree = pivot.right;
            
            left = subtree;
            if( subtree!=null ) subtree.parent = this;
            
            parent = pivot;
            pivot.right = this;
            
            if( p==null )root = pivot;   
            else if( p.left == this )p.left = pivot;
            else p.right = pivot;   

            pivot.parent = p;
            
            recalc();
            pivot.recalc();
            if( p!=null ) p.recalc();
        }

        /**
         * Insert a node into the subtree rooted here.
         * 
         * @param node Node to insert
         */
        public void insert( Node node )
        {
            if( node.value <= value )
            {
                // If this node has no left subtree, then insert here.
                if( left==null )
                {
                    left = node;
                    node.parent = this;
                    
                    // If we're inserting the new node to the left of this node,
                    // then the new value is immediately previous
                    // to this node in the sorted linked list.
                    Node prevnode = prev;
                    node.next = this;
                    node.prev = prevnode;
                    prev = node;
                    if( prevnode!=null ) prevnode.next = node;                   
                }
                else
                {
                    left.insert( node );
                }
            }
            else
            {
                // If this node has no right subtree, then insert here.
                if( right==null )
                {
                    right = node;
                    node.parent = this;
                    
                    // If we're inserting the new node to the right of this node,
                    // then the new value is immediately following
                    // this node in the sorted linked list.
                    Node nextnode = next;
                    node.prev = this;
                    node.next = nextnode;
                    next = node;
                    if( nextnode!=null ) nextnode.prev = node;                   
                }
                else
                {
                    right.insert( node );
                }
            }
            
            balance();
        } 
        
        /**
         * Find a node in the tree.
         * 
         * @param target Value to find
         * @return Node with value=target, or the closest we can find
         */
        public Node find( int target )
        {
            Node result = this; 
            if( target<value )
            {
                if( left!=null ) result = left.find( target );
            }
            else if( target>value )
            {
                if( right!=null ) result = right.find( target ); 
            }
            
            return result;
        }
                
        /**
         * Delete a node.
         * 
         * @param target Value of the node to delete.
         */
        public void delete( int target )
        {
            if( target==value )
            {
                // This is the node to delete. First, take it out of the linked list.
                if( next!=null ) next.prev = prev;
                if( prev!=null ) prev.next = next;
                
                // Find a replacement node to put in this node's place
                Node replacement = null;
                if( left==null )
                {
                    replacement = right;;
                }
                else if( right==null )
                {
                    replacement = left;
                }
                else
                {
                    recalc();                    
                    replacement = leftheight()>=rightheight() ? prev : next;
                    
                    if( replacement==left )
                    {
                        replacement.right = right;
                        right.parent = replacement;
                    }
                    else if( replacement==right )
                    {
                        replacement.left = left;
                        left.parent = replacement;
                    }
                    else if( replacement!=null )
                    {
                        Node kid = replacement.left==null ? replacement.right : replacement.left;
                        if( replacement.parent.left==replacement ) replacement.parent.left = kid; 
                        else replacement.parent.right = kid;
                        if( kid!=null ) kid.parent = replacement.parent;
                        
                        for( Node node = replacement.parent; node!=this && node!=null; node = node.parent )
                        {
                            node.balance();
                        }
                        
                        replacement.left = left;
                        replacement.right = right;
                        left.parent = replacement;
                        right.parent = replacement;
                    }
                }
                   
                if( replacement!=null && replacement.parent==parent ) System.err.println( "PANIC!!" );
                if( parent==null ) root = replacement;
                else if( parent.left==this ) parent.left = replacement;
                else parent.right = replacement;
                
                if( replacement!=null )replacement.parent = parent;
                                
                parent = left = right = next = prev = null;
            }
            // We haven't found the node to delete yet.
            // Keep looking.
            else if( target<value  )
            {
                left.delete( target );
            }
            else
            {
                right.delete( target );
            }
            
            balance();
        }
                
        /**
         * Perform AVL balancing on this node.
         */
        private void balance()
        {
            recalc();
            
            // Perform AVL balancing
            if( leftheight()-rightheight()>1 )
            {
                if( left.rightheight()>left.leftheight() )
                {
                    left.rotateleft(); 
                }
                rotateright();
            }
            else if( rightheight()-leftheight()>1 )
            {
                if( right.leftheight()>right.rightheight() )
                {
                    right.rotateright();
                }
                rotateleft();   
            }
            
        }
        
        /**
         * Print a pretty string for debugging.
         * 
         * @return An inorder traversal of the subtree rooted here.
         */
        public String toString()
        {
            String inorder = "";
            if( left!=null ) inorder += left.toString();
            inorder += value + " ";
            if( right!=null ) inorder += right.toString();
            
            return inorder;
        }
    }
    
    /** 
     * We'll store all usages of primes in AVL-balanced binary
     * search trees. These are the trees and a helpful root. 
     * For each prime, we'll use an AVL tree to store/find 
     * indices of values in the sequence that contain that prime.
     */
    public Node root;
    public Node trees[] = new Node[10000];

    /** The intervals and sums for a segment tree. */
    public int intervals[] = new int[1000000];
    public int sums[] = new int[1000000];
    /** 
     * Some helpful boolean variables to help us see
     * if a given prime is in the old or new values when
     * Andrew makes a change
     */
    public boolean ina[] = new boolean[10000];
    public boolean inb[] = new boolean[10000];

    /**
     * Adjust a segment tree with lazy propagation.
     * 
     * @param lo Low index of the range we're changing.
     * @param hi High index of the range we're changing.
     * @param min Low index of the range at this node.
     * @param max High index of the range at this node.
     * @param index Index of this node.
     * @param delta Change to make
     * @throws Exception
     */
    public void adjust( int lo, int hi, int min, int max, int index, int delta ) 
    {
        int left = index+index;
        int right = left+1;
        
        if( lo<=min && max<=hi )
        {
            // If [min,max] is entirely in [lo,hi] then there's no need
            // to go any further. Just stop here and adjust the interval.
            intervals[index] += delta;
        }
        else
        {
            // Otherwise, break into two subintervals. Only
            // traverse if the subinterval intersects [lo,hi]
            int mid = (min+max)/2;
            if( min<=hi && lo<=mid ) adjust( lo, hi, min, mid, left, delta );
            if( mid+1<=hi && lo<=max ) adjust( lo, hi, mid+1, max, right, delta );
        }
        
        // Maintain sums simultaneously. 
        // If this interval is full of endpoints, then its full range
        // is the number of k-sized intervals represented. Otherwise, look to its children.
        sums[index] = (intervals[index]>0) ? max-min+1 : sums[left] + sums[right];
    }
        
    /**
     * Driver.
     * @throws Exception
     */
    public void doit() throws Exception
    {
        BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) ); //new FileReader( "fantastic.in" ) );
        ps = System.out; //new PrintStream( new FileOutputStream( "fantastic.out" ) );
        
        // Precompute primes.
        boolean isprime[] = new boolean[100000];
        Arrays.fill( isprime, true );
        isprime[0] = isprime[1] = false;
        np = 0;
        for( int i=2; i<100000; i++ ) if( isprime[i] )
        {
            primes[np++] = i;
            for( int j=i+i; j<100000; j+=i )
            {
                isprime[j] = false;
            }
        }
        
        // Break every possible input number
        // into its prime factors.
        // We'll use an index into the primes[] array,
        // and we'll use -1 as a sentinel for the 
        // end of the list. We'll only
        // list each prime once - that's all we need.
        for( int i=1; i<=100000; i++ )
        {
            int f=0;
            int number=i;
            for( int j=0; number>1; ++j )
            {
                int p = primes[j];
                if( number%p==0 )
                {
                    factors[i][f++] = j;
                    while( number%p==0 ) number/=p;
                }
            }
            factors[i][f] = -1;
        }
        
        String tokens[];
        for(;;)
        {
            tokens = br.readLine().split( "\\s+" );
            n = Integer.parseInt( tokens[0] );
            k = Integer.parseInt( tokens[1] );
            m = Integer.parseInt( tokens[2] );
            if( n==0 ) break;
            
            Arrays.fill( intervals, 0 );
            Arrays.fill( sums, 0 );
            Arrays.fill( last, -1 );
            Arrays.fill( trees, null );
            
            // First, we'll read Andrew's original list
            long sum = 0L;
            for( int i=0; i<n; i++ )
            {
                sequence[i] = Integer.parseInt( br.readLine() );
                
                // Fantastic!
                sum += sequence[i];
                
                // For each prime factor, we'll see if that prime factor
                // occurs close enough in the recent past to
                // create some k-sized intervals
                for( int f=0; ; f++ )
                {
                    int p = factors[sequence[i]][f];
                    if( p<0 ) break;
                    
                    if( last[p]>=0 && i-last[p]<k )
                    {
                        int lo = Math.max( i, k-1 );
                        int hi = Math.min( last[p]+k-1, n-1 );
                        
                        // Everything from lo to hi is the top limit
                        // of a k-sized interval which violates
                        // the all-coprime constraint
                        adjust( lo, hi, 0, n-1, 1, 1 );
                    }  
                    
                    // Put a new node for this index into the AVL tree
                    // for this prime. We'll use this to efficiently find
                    // the last occurrence of a prime when we're implementing
                    // Andrew's changes
                    Node node = new Node( i );
                    if( trees[p]==null )
                    {
                        trees[p] = node;
                    }
                    else
                    {
                        root = trees[p];
                        root.insert( node );
                        trees[p] = root;
                    }

                    // This index is now the last occurrence of this prime.
                    last[p] = i;
                }
            }
            ps.println( sums[1] );
   
            // Now, we'll implement Andrew's changes
            for( int i=0; i<m; i++ )
            {
                tokens = br.readLine().split( "\\s+" );
                int a = Integer.parseInt( tokens[0] )-1;
                int b = Integer.parseInt( tokens[1] );
                int sa = sequence[a];
                
                // Adjust the sum.
                // Remember, that's Andrew's Fantastic Problem!
                sum += b - sa;
                
                // Keep track of which primes are in B.
                // We'll need this later.
                for( int f=0; ; f++ )
                {
                    int p = factors[b][f];
                    if( p<0 ) break;
                    inb[p] = true;
                }
                
                // Go through all of sequence[a]'s prime factors
                for( int f=0; ; f++ )
                {
                    int p = factors[sa][f];
                    if( p<0 ) break;
                    
                    // Record that this prime is in sequence[a].
                    // We'll need this later.
                    ina[p] = true;
                    
                    // If this factor is also in B, 
                    // then there's nothing we need to do.
                    if( inb[p] ) continue;
                    
                    // Look for the previous instance of this prime.
                    // This is where the AVL trees are handy!
                    root = trees[p];
                    Node node = root.find( a );
                    if( node.prev!=null )
                    {
                        // This prime will no longer be in sequence[a].
                        // So, if there's a previous instance of this prime that's
                        // in range, there are a bunch of intervals that will no longer
                        // be there.
                        int lastp = node.prev.value;
                        if( a-lastp<k )
                        {
                            int lo = Math.max( a, k-1 );
                            int hi = Math.min( lastp+k-1, n-1 );
                            adjust( lo, hi, 0, n-1, 1, -1 );
                        }                    
                    }
                    
                    if( node.next!=null )
                    {
                        // This prime will no longer be in sequence[a].
                        // So, if there's a *next* instance of this prime that's
                        // in range, there are a bunch of intervals that will no longer
                        // be there.
                        int nextp = node.next.value;
                        if( nextp-a<k )
                        {
                            int lo = Math.max( nextp, k-1 );
                            int hi = Math.min( a+k-1, n-1 );
                            adjust( lo, hi, 0, n-1, 1, -1 );
                        }  
                        
                        if( node.prev!=null )
                        {
                            // If the previous and the next are in range of each other,
                            // then some intervals may need to be added back in.
                            int lastp = node.prev.value;
                            if( nextp-lastp<k )
                            {
                                int lo = Math.max( nextp, k-1 );
                                int hi = Math.min( lastp+k-1, n-1 );
                                adjust( lo, hi, 0, n-1, 1, 1 );
                            }                    
                        }

                    }
                    
                    // Delete this index from this prime's tree
                    root.delete( a );
                    trees[p] =  root;
                }
                
                // Make the change!
                sequence[a] = b;
                
                // We've accounted for the removal of sequence[a],
                // now we've got to account for adding b to the mix.
                for( int f=0; ; f++ )
                {
                    int p = factors[b][f];
                    if( p<0 ) break;
                    
                    // Again, if this prime is also in the old sequence[a], 
                    // then there's nothing we need to do.
                    if( ina[p] ) continue;
                    
                    // Create a new node, and put it in p's tree!
                    Node node = new Node( a );
                    if( trees[p]==null )
                    {
                        trees[p] = node;
                    }
                    else
                    {
                        root = trees[p];
                        root.insert( node );
                        trees[p] = root;
                    }
                    
                    if( node.prev!=null )
                    {
                        // If the previous instance of this prime is in range,
                        // we've got some intervals to add!
                        int lastp = node.prev.value;
                        if( a-lastp<k )
                        {
                            int lo = Math.max( a, k-1 );
                            int hi = Math.min( lastp+k-1, n-1 );
                            adjust( lo, hi, 0, n-1, 1, 1 );
                        }                    
                    }
                    
                    if( node.next!=null )
                    {
                        // If the next instance of this prime is in range,
                        // we've got some intervals to add!
                        int nextp = node.next.value;
                        if( nextp-a<k )
                        {
                            int lo = Math.max( nextp, k-1 );
                            int hi = Math.min( a+k-1, n-1 );
                            adjust( lo, hi, 0, n-1, 1, 1 );
                        }
                        
                        if( node.prev!=null )
                        {
                            // If the previous instance is in range, we
                            // might end up double-counting, and that's bad,
                            // so we've got some intervals to remove.
                            int lastp = node.prev.value;
                            if( nextp-lastp<k )
                            {
                                int lo = Math.max( nextp, k-1 );
                                int hi = Math.min( lastp+k-1, n-1 );
                                adjust( lo, hi, 0, n-1, 1, -1 );
                            }                    
                        }

                    }
                }
                
                // Reset inb[]
                for( int f=0; ; f++ )
                {
                    int p = factors[b][f];
                    if( p<0 ) break;                    
                    inb[p] = false;
                }
                
                // Reset ina[]
                for( int f=0; ; f++ )
                {
                    int p = factors[sa][f];
                    if( p<0 ) break;                    
                    ina[p] = false;
                }
                
                // Print the new number of bad intervals
                ps.println( sums[1] );
            }
            
            // Fantastic!
            ps.println( sum );
        }
    }
    
    /**
     * @param args
     */
    public static void main( String[] args ) throws Exception
    {
        //long start = System.currentTimeMillis();
        new fantastic_vanb().doit();     
        //System.out.println( ""+(System.currentTimeMillis() - start) );
    }   
}