// Arup Guha
// 4/1/2016
// Solution to 2014 NAIPC Problem D: Fantastic Problem

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

public class d {

	public static int n;
	public static int range;
	public static int numQueries;
	public static int[] res;
	public static int[] nums;
	public static IntTree myTree;

	public static ArrayList[] primeList;
	public static TreeSet[] primeIndexList;

	final public static int MAX = 100001;

	public static void main(String[] args) throws Exception {

		// Useful...
		populatePrimeList();

		// Read in first case.
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tok = new StringTokenizer(stdin.readLine());
		n = Integer.parseInt(tok.nextToken());
		range = Integer.parseInt(tok.nextToken());
		numQueries = Integer.parseInt(tok.nextToken());

		int sumQ = numQueries;
		int loop = 0;

		// Process each case.
		while (n != 0) {

			// Read in the numbers.
			long sum = 0;
			nums = new int[n];
			for (int i=0; i<n; i++) {
				nums[i] = Integer.parseInt(stdin.readLine().trim());
				sum += nums[i];
			}

			// pIL[i] stores which indexes are divisible by i (only if i is prime).
			primeIndexList = new TreeSet[MAX];
			for (int i=0; i<MAX; i++)
				primeIndexList[i] = new TreeSet<Integer>();

			// Set up my interval tree.
			myTree = new IntTree(0, n-range);

			// Solve the initial problem.
			int initRes = getNumInvalid();

			// Now, process queries.
			res = new int[numQueries];
			for (int i=0; i<numQueries; i++) {

				// Read in the query.
				tok = new StringTokenizer(stdin.readLine());
				int index = Integer.parseInt(tok.nextToken())-1;
				int newVal = Integer.parseInt(tok.nextToken());
				int delta = newVal - nums[index];

				// Process this change for the interval tree.
				process(index, nums[index], newVal);

				// Our result...
				res[i] = n-range+1 - myTree.query(0, n-range);

				// Update sum and change the value.
				sum += delta;
				nums[index] = newVal;
			}

			// Put together answer and write it out!
			StringBuffer sb = new StringBuffer();
			sb.append(initRes+"\n");
			for (int i=0; i<numQueries; i++)
				sb.append(res[i]+"\n");
			sb.append(sum+"\n");
			System.out.print(sb);

			// Get next case.
			tok = new StringTokenizer(stdin.readLine());
			n = Integer.parseInt(tok.nextToken());
			range = Integer.parseInt(tok.nextToken());
			numQueries = Integer.parseInt(tok.nextToken());
			sumQ += numQueries;
			loop++;
		}
	}

	public static void process(int index, int oldVal, int newVal) {

		ArrayList<Integer> common = getCommon(primeList[oldVal], primeList[newVal]);

		// First remove each pair this item is associated with.
		for (int i=0; i<primeList[oldVal].size(); i++) {

			// Store this prime.
			int thisP = (Integer)(primeList[oldVal].get(i));

			// No need to change since it's in both numbers.
			if (common.contains(thisP)) continue;

			// Remove left consecutive interval, if necessary.
			Integer prevI = (Integer)(primeIndexList[thisP].lower(index));
			if (prevI != null && index-prevI < range) myTree.change(Math.max(0,index-range+1), Math.min(n-range,prevI), -1);

			// And right consecutive interval.
			Integer nextI = (Integer)(primeIndexList[thisP].higher(index));
			if (nextI != null && nextI-index < range) myTree.change(Math.max(0,nextI-range+1), Math.min(n-range,index), -1);

			// Tricky case - a new interval might be created, we must add this in.
			if (prevI != null && nextI != null && nextI-prevI < range) myTree.change(Math.max(0, nextI-range+1), Math.min(n-range, prevI), 1);

			// Update the appropriate tree set.
			primeIndexList[thisP].remove(index);
		}

		// Now add in new intervals for the primes in this number.
		for (int i=0; i<primeList[newVal].size(); i++) {

			// Store this prime.
			int thisP = (Integer)(primeList[newVal].get(i));

			// Same deal as before.
			if (common.contains(thisP)) continue;

			// Add interval to left, if necessary.
			Integer prevI = (Integer)(primeIndexList[thisP].lower(index));
			if (prevI != null && index-prevI < range) myTree.change(Math.max(0,index-range+1), Math.min(n-range,prevI), 1);

			// And to right side.
			Integer nextI = (Integer)(primeIndexList[thisP].higher(index));
			if (nextI != null && nextI-index < range) myTree.change(Math.max(0,nextI-range+1), Math.min(n-range,index), 1);

			// Tricky symmetric case - this might have been in the count, get rid of these.
			if (prevI != null && nextI != null && nextI-prevI < range) myTree.change(Math.max(0, nextI-range+1), Math.min(n-range, prevI), -1);

			// Update the appropriate tree set.
			primeIndexList[thisP].add(index);
		}
	}

	// Returns the intersection of a and b.
	public static ArrayList<Integer> getCommon(ArrayList<Integer> a, ArrayList<Integer> b) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		for (Integer x: a)
			if (b.contains(x))
				res.add(x);
		return res;
	}

	// Returns the number of initially invalid intervals.
	public static int getNumInvalid() {

		// Go through each number.
		for (int i=0; i<n; i++) {

			// Now, process each unique prime factor of this number.
			for (int j=0; j<primeList[nums[i]].size(); j++) {

				int thisP = (Integer)(primeList[nums[i]].get(j));

				// Note that prime thisP divides evenly into nums[i].
				primeIndexList[thisP].add(i);

				Integer prevLast = (Integer)(primeIndexList[thisP].lower(i));

				// Update, if necessary, how long ranges will not be coprime.
				if (prevLast != null && prevLast > i-range) myTree.change(Math.max(0,i-range+1), Math.min(prevLast,n-range), 1);
			}
		}

		// Here is our result.
		return n-range+1-myTree.query(0,n-range);
	}

	public static void populatePrimeList() {

		// Runs modified prime sieve to fill unique list of prime factors for each integer.
		primeList = new ArrayList[MAX+1];
		for (int i=0; i<=MAX; i++)
			primeList[i] = new ArrayList<Integer>();

		for (int i=2; i<=MAX; i++)
			if (primeList[i].size() == 0)
				for (int j=i; j<=MAX; j+=i)
					primeList[j].add(i);
	}
}

class IntTree {

	// Stores range for this node.
	public int low;
	public int high;

	// Stores aggregate data for this node.
	public int delta;
	public int value;
	public int minFreq;

	// Pointers to children.
	public IntTree left;
	public IntTree right;

	// Creates an interval tree from myLow to myHigh, inclusive.
	public IntTree(int myLow, int myHigh) {

		low = myLow;
		high = myHigh;
		delta = 0;
		value = 0;
		minFreq = myHigh-myLow+1;

		// Lowest level.
		if (low == high) {
			left = null;
			right = null;
		}

		// Must create more nodes.
		else {
			int mid = (low+high)/2;
			left = new IntTree(low, mid);
			right = new IntTree(mid+1, high);
		}
	}

	// Propogates a change down to child nodes.
	public void prop() {

		// Recursive case, push down.
		if (left != null) {
			left.delta += delta;
			right.delta += delta;
			delta = 0;
		}
	}

	// Pre-condition: delta is 0.
	public void update() {
		if (left != null) {
			int minLeft = left.value+left.delta;
			int minRight = right.value+right.delta;
			value = Math.min(minLeft, minRight);
			if (minLeft < minRight)
				minFreq = left.minFreq;
			else if (minRight < minLeft)
				minFreq = right.minFreq;
			else
				minFreq = left.minFreq + right.minFreq;
		}
	}

	// Changes the values in the range [start, end] by "adding" extra.
	public void change(int start, int end, int extra) {

		// Out of range.
		if (high < start || end < low) return;

		// Push down delta.
		prop();

		if (start <= low && high <= end) {
			delta += extra;
			update();
			return;
		}

		// Portions of children have to be changed instead.
		left.change(start, end, extra);
		right.change(start, end, extra);
		update();
	}

	public int query(int start, int end) {

		// Out of range.
		if (high < start || end < low) {
			return  0;
		}

		// Whole range must be returned;
		if (start <= low && high <= end) {
			return value+delta == 0 ? minFreq : 0;
		}

		// Get answers from both potions.
		prop();
		int leftSide = left.query(start, end);
		int rightSide = right.query(start, end);
		update();
		return leftSide+rightSide;
	}
}