Description

对于一个只含小写字母的字符串，我们认为其压缩长度为连续相同字母序列段的个数。例如串"aabcaaaa"的压缩长度为4：第一组连续相同字母序列段为2个"a",第二组为1个"b"，第三组为1个"c",第四组为4个"a"。设串原长为s,前n个字符看成是在同一个块中，接下来的n个字符(即第n+1到第2n个字符)也看成是在同一个块中，再接下来的n也这样……这样就将串分成s/n个块(保证s能被n整除)，接下来会有m次操作，每个操作给出两个整数x,y，每次操作都对串中的每一个块内的第x个字符和第y个字符交换。例如原串"aabcasda",n==4,第一次操作为(2,3)，新生成的串为"abacadsa",第二次操作为(1,2),则又生成"baacdasa"，月光想知道每次操作后新生成的串的压缩长。

Input

每组数据第一行给出一个字符串，串长s<=50000 第二行给出一个正整数n,2<=n<=16 第三行给出一个正整数m,表示操作次数，m<=50000 接下来的m行，每行两个正整数x,y 1<=x,y<=n ,x!=y

Output

对每组数据，首先输出原串的压缩长，然后对每次操作，输出操作后串的压缩长.

Sample

Input

abab
2
1
1 2
moonlight
3
2
2 3
1 2

Output

4
4
8
8
9

Source: DK