2013: 分组行动

最近，木木中学要举行一年一度的辩论赛了，我们活泼开朗乐观向上不寂寞不生病不挂科天天回家吃饭的新时代好少年――飞飞，自然是热情参与咯！辩论嘛，就有正方和反方两个组，这是一个传统项目，所以，包括飞飞，木木中学的每一个学生都会加入2个组中的一个，不会有人打酱油的（如果有人打酱油，那么飞飞会义无反顾义不容辞的上前用一翻惊天动地的演说打消他打酱油的念头的）。

自然啦，作为有思想有文化能言善辩的好少年，飞飞，其实加入哪个组，从技术角度分析真是无所谓的，不过呢，从另外一些角度来看，就复杂的多了……

比如，飞飞是个很不喜欢八卦的正义青年，所以啊，飞飞很不想和年级最PP的女生青菜分在一个组，因为会产生八卦的――为什么会有八卦？首先是他们比较熟（比较熟就会有八卦吗？无限yy中……），最重要的就是因为飞飞是大帅哥啊！人长得帅，有时候真是挺麻烦的，尤其飞飞还如此低调……

再比如，飞飞也不想和小邱分在一个组――虽然他们不认识，但是，飞飞听说小邱很懒还很暴力，飞飞不喜欢暴力……

当然了，不论如何的分组行动，都会产生一些代价的，比如两个好朋友分在了不同的组，那肯定不是很高兴了。

飞飞知道，学校里有M对同学是相互认识的，每对认识的同学间，都有一个要好程度C，自然的，关系越好，要好程度越高，也越不愿意分开。对于一个分组方案，必然会使得有某些认识的同学分开，飞飞认为，一个分组方案的代价就是最不愿意分开的那两个同学之间的要好程度。

飞飞在想，和青菜MM分在不同的组最小代价是多少呢？和小邱同学分在不同的组最小代价是多少呢？如果……还要将青菜MM和小邱分在不同的组最小代价是多少呢？……好麻烦啊，飞飞越想越乱，于是来找你帮忙了。

一些说明：

木木中学有N个学生，木木中学是一所优秀的中学，学生们都是开朗外向的，所以一个学校里任意两个学生间接或者直接肯定认识。

显然任意一个辩论组都至少得有一个人。

为了方便，我们把木木中学的学生用1到N编号，飞飞有Q个问题，每个问题的形式都是这样的：将编号为a的学生与编号为b的学生分在不同组中，最少的代价是多少呢？

关于这道题目本身，只是想检验你能不能帮飞飞，所以你并不需要――具体回答每个问题，只需要最后输出每个问题答案的乘积除以P的余数就可以了。

输入文件中的第一行为四个正整数N，M，Q，P。

第二行至第M+1行，每行有三个正整数a，b，c，表示编号为a的同学和编号为b的同学认识，并且要好程度是c。保证a和b是不会相同的，也不会有多行描述相同两个学生之间的关系。

第M+2行至第M+Q+1行，每行有两个正整数a，b，表示飞飞的一个问题，这里保证a和b是不同的。

输出文件中仅一行为一个整数，所有问题答案的乘积除以P的余数。

3 3 2 21
1 2 3
2 3 4
1 3 5
1 2
2 3

16