公主の#18文明游戏

题目背景

公主发现了一个游戏,998,于是我就花钱给她买下来了(捂脸)

题目描述

这个游戏叫做《文♂明》(滑稽),但是跟平常意义上的不一样。 这个游戏里有n个城市,标号1~n,有m条双向道路相连,编号1~m。 游戏里会系统会添加Ni个人到一个城市Xi,并给定这些人的信仰Ci 系统还会切断一条道路,并给定道路编号Xi 系统还会给定一个城市Xi,询问从Xi出发可以到达的所有城市中选择Ni个人, 使得他们信仰都为Ci的概率为多少,对19260817取模。 输入数据不保证没有重边和自环。 输入数据不保证同一条边不会被切断两次以上。 因为是公主的游戏,所以本题输入量较大,请注意输入的优化

输入输出格式

输入格式


第一行三个正整数n,m,q 接下来n行,每行两个正整数Ni,Ci,分别代表第i个城市初始人数和信仰 接下来m行,每行两个正整数Xi,Yi,分别代表这条道路的起点和终点 接下来q行,每行第一个正整数opt(1<=opt<=3) 当opt=1时,表示系统添加人类,输入三个整数Xi,Ni,Ci 当opt=2时,表示系统切断道路,输入一个整数Xi 当opt=3时,表示系统询问概率,输入三个整数Xi,Ni,Ci

输出格式


对于每一个opt=3的操作,输出一行一个整数。

输入输出样例

输入样例 #1

5 5 5
5 1
9 2
8 1
8 1
6 2
5 2
1 2
2 2
1 1
5 3
1 1 3 2
2 1
3 3 4 1
3 2 3 1
3 1 2 1

输出样例 #1

9293681
15578602
849742

说明

吐槽某人居然没告诉我 我没放样例 补发样例(其实我本来有样例来着) 在这里跟大家道歉 对于30%的数据,1<=n,m,q<=100 对于60%的数据,1<=n,m,q<=50000 对于100%的数据,1<=n,m,q<=400000 对于100%的数据,保证所有信仰在C++的int,Pascal的long int范围内 对于100%的数据,保证每次添加的人数和初始人数都不超过10 对于100%的数据,保证数据随机生成 题目 @玫葵之蝶