定义数位和是一个数字中每一个数位的和，例如数字 123 的数位和是 1+2+3=6，数字 1024 的数位和是 1+0+2+4=7。

鸡尾酒和玥玥的生日连起来是 512417，这个数字的数位和是 5+1+2+4+1+7=20，恰好是 10 的倍数。所以鸡尾酒定义：如果某一个数字的数位和恰好是 10 的倍数，那么我们称它为一个“鸡尾酒数”。

给定 ，请问  （即 到 之间所有整数）这些数字中有多少个鸡尾酒数，由于结果可能很大，请输出答案对 取模后的结果。

题目出到这里，鸡尾酒深感这样的难度远远无法满足参与小白玥赛的众位小白之王，于是加入了单点修改的机制。再给定 次询问，每次询问给出两个数字 ，表示将  的数位中从左往右的第 位修改为数字 ，再问 中有多少个鸡尾酒数。对于每次询问你都需要回答一次这个问题。

请注意：每次询问时的修改都会永久生效；一个数字最左边的一位记为第一位。

输入一行包含一个整数  和一个正整数 ，其中  表示询问的次数。

接下来包含  行，每行给出两个整数 ，保证修改之后的数字不包含前导零，其中  为数字  的长度。

输出  行，第一行的数字表示答案对  取模后的结果。

之后对于每一次询问给出一个回答，同样输出答案对  取模之后的结果。

1 0

0

样例在询问 1 到 1 之间有多少个鸡尾酒数。1 的数位和是 1，不是 10 的倍数，所以没有鸡尾酒数。此样例没有修改的操作，所以只需输出一行。

102 2
3 9
2 1

9
10
11

首先输出 9 表示  中有 9 个鸡尾酒数；第一次修改将第三个位置改为 9，此时  变为 109，输出 10 表示  中有 10 个鸡尾酒数。第二次修改在之前的基础上将第二个位置改为 1，即  被修改为 119，此时输出 11 表示  中有 11 个鸡尾酒数。