2007年10月5日，我举办了一次NOIp模拟赛。现在比赛已经顺利结束了，以下是这次比赛的题目

题目一览

题目名称    Matrix67的情书（二）  送给MM的生日礼物   流言的传播         表白机器人
题目类型    传统                  传统               传统               传统
源文件名称  lovelttr.(pas/c/cpp)  gift.(pas/c/cpp)   rumor.(pas/c/cpp)  robot.(pas/c/cpp)
输入文件名  lovelttr.in           gift.in            rumor.in           robot.in
输出文件名  lovelttr.out          gift.out           rumor.out          robot.out
时间限制    1秒                   1秒                1秒                1秒
内存限制    64M                   64M                64M                64M
测试点      10个                  10个               10个               10个
分值        100分                 100分              100分              100分

Problem 1: lovelttr
Matrix67的情书（二）

问题描述
    28是一个很特别的数字。它是一个完全数，是一个三角形数，是前五个素数的和。天上有28星宿，人有28颗牙齿；土星绕太阳公转一周需要28年，从一只猴子的释放到整座城市的沦陷只需28天。当然，Matrix67偏爱这个数字是有原因的：这是一个关心MM身体和计算安全期都必须用到的数字。总之，Matrix67非常喜欢数字28，他甚至希望数字28能够出现在他给MM写的情书里。
    Matrix67的情书只由数字、大小写字母、空格、换行符和各种英文半角标点符号组成。除去所有其它的字符，仅保留文本中的数字和字母，则整个情书可以看作是一个36进制数。比如，句子“I Love you!”可以转化为1457771337246，因为(ILOVEYOU)36 = (1457771337246)10。Matrix67希望从情书中截取一个或若干个连续的句子，使得它所对应的十进制数能够被28整除。Matrix67希望知道他的情书中有多少个文本片段满足这样的条件。
    我们认为，只有句号、感叹号、问号三种符号才是句子结束的标志（当然整篇文章的结束也标志着最后一句话结束，即使文章最末尾没有任何标点符号）。Matrix67的情书里保证没有不能表示任何数字的“空句子”，即任意两个句子结束标志之间至少会出现一个数字或字母。

输入数据
    输入数据是一篇合法的英文文章，包括英文大小写字母、数字、空格、回车和半角的标点符号。

输出数据
    输出满足要求的文本片段个数。一个满足要求的文本片段是指一个或若干个连续的句子，将它们当作36进制后得到的数可以被28整除。

样例输入

I WILL SHOW YOU

Yes, I am still amazed that I have you. It's still hard to understand how you chose me. How after just one short conversation you knew I was meant for you. But now I know the truth of your conviction. I've never been with someone who suited me so perfectly. You seduced me with your sexy body and strong spirit, and you've kept me with your tender heart. I know you that I can't have you completely and maybe not even for much longer. But I'm still happy. A part of you has become part of me and that is enough.

You'll laugh when I say this, but I dream about you every night. Probably because I can't see you often enough. But when I'm awake I know that you are the furthest thing from a dream. Sometimes I imagine that you are built from solid rock: a moving statue and an indestructible human being. You absolutely contain yourself and then again much more than yourself. Your confidence is consuming and your perspective is huge. You have no place in your life for jealousy or complaints. My friends seem so small in comparison, with their problems always spilling over onto everyone else.

I want you to know how much you've opened my eyes and helped me truly see myself. Until now, my life has been an undecided back-and-forth, and now I know that I've wasted too much time. But now my direction seems clear, and I have confidence in my future. The past doesn't seem to matter anymore. You've made me see possibilities I would never have imagined before.

Yes, I want to please you. But it's through pleasing you that I'll become a better and stronger person. There is nothing I want more than to transform myself through you. You challenge me to grow beyond myself and leave my weaker self behind. I will show you how beautiful I can be, and I will show you how brilliant I can become. This way, I know I'll always have your love.

Forever yours,

Matrix67

样例输出
6

数据规模
    对于30%的输入数据，输入文件大小不超过50KB；
    对于100%的输入数据，输入文件大小不超过1MB。

Problem 2: gift
送给MM的生日礼物

问题描述
    10月11日是MM的生日，Matrix67打算自己DIY一些抱枕送给MM。Matrix67手中有一块矩形花布，花布分成了M x N个小格子，有些格子的花色相同，有些格子的花色不同。为了使最终成品更美观，Matrix67希望用于DIY的布匹都是正方形的，并且满足布匹花色上下对称且左右对称。为此，他希望能计算出这块花布里一共包含有多少个上下对称且左右对称的小正方形。
    举例来说，Matrix67手中的花布大小为6 x 4，上面共有5种花色：

ABACDA
DCDEAA
ABABAA
DDCBBA

    则这块布里一共有26个上下对称且左右对称的正方形，其中包括最左上角的3×3正方形、右边4个A组成的2×2正方形，当然还有24个1×1的小正方形。

输入数据
    第一行输入两个用空格隔开的正整数M,N，表示Matrix67手中的格子布分为M行N列。
    以下M行每行N个字符，描述布匹的花色。我们用26个大写字母来区别不同的花色，相同的字母代表相同的花色，不同的字母代表不同的花色。

输出数据
    输出在Matrix67的格子布中切出一块花色左右对称且上下对称的正方形共有多少种方案。

样例输入
4 6
ABACDA
DCDEAA
ABABAA
DDCBBA

样例输出
26

数据规模
    对于30%的数据，M,N<=10；
    对于100%的数据，M,N<=200。

Problem 3: rumor
流言的传播

问题描述
    昨天下午，Matrix67陪MM出去逛街，走累了后去咖啡店歇了歇脚；再后来MM陪Matrix67去了一趟书店，之后两人去电影院看了一场电影。从电影院出来后已经很晚了，考虑到MM的安全问题，Matrix67先送MM回到宿舍，然后自己才回去。第二天Matrix67起床后发现问题严重了：昨天和MM出去玩本来什么都没发生，但现在一些不堪入耳的流言正疯狂传播，很多细节都说得有鼻子有眼的。在澄清事实并抓出元凶的同时，Matrix67希望切断一些流言传播的路径，尽可能减缓流言传播的速度。
    除去Matrix67和他的MM，学校里还有N个人。这N个人形成了M对双向的朋友关系，这些朋友关系连通了所有N个人。不同的朋友间传递消息的速度各不相同。如果A和B是第i对朋友，那么当其中一个人听到流言后，他会在Ti的时间内传给另一个人。现在，Matrix67只知道流言并没有传遍整个学校，但他不知道哪些人已经听说了这个流言。他希望切断尽可能少的朋友关系，使得无论是哪些人已经获知了流言，流言都无法以原来的速度传给一个新的人（即新的得知此流言的人的出现将变得更晚）。换句话说，Matrix67希望找到一个最小的边集E，使得对任意一个不等于全集的点集S，恰好只有一个顶点在S里的边中权值最小的那一条在边集E中。

输入数据
    第一行输入两个用空格隔开的正整数N和M，分别表示学校的人数和朋友关系数。
    以下M行每行有三个用空格隔开的正整数，其中第i行的三个正整数为Ai, Bi, Ti，表示Ai和Bi是第i对朋友，它们之间传递消息需要Ti的时间。输入数据保证0<Ai≠Bi<=N，0<Ti<=2 000 000 000，且对任意i≠j都有Ti≠Tj。

输出数据
    你需要输出你所得到的最小值和具体的方案。
    输出文件的第一行是一个正整数，代表你的最优方案中需要切断的朋友关系数。
    以下若干行每行一个正整数，表示你的方案里需要切断的朋友关系在输入数据中的编号（即你需要切断的是输入数据中给的第几条边）。这些数必须按照增序排列输出。
    如果有多种最优方案，你只需要输出其中一种即可。我们的评测系统会自动判断你的输出数据的正确性。

样例输入
4 4
1 2 2
4 3 4
2 3 3
1 3 1

样例输出
3
1
2
4

样例说明
               (1)
                o
               /
            1 /   2
             /    
(4) o——-o——-o (2)
        4  (3)  3  

    首先，(3)—(4)这条边必须去掉，否则若只有4号同学得知流言，流言将以相同的速度传给下一个人。对于其它三条边，只需要去掉权值较小的两条即可，这样不论获知流言的是哪个（些）人，所有可以继续向外传播流言的边中最小的那一条一定已经被去掉了。可以证明，去掉三条边已经是最优的答案了。

数据规模
    对于30%的数据，N<=10，M<=20；
    对于50%的数据，N<=100，M<=1 000；
    对于100%的数据，N<=10 000，M<=100 000。

Problem 4: robot
表白机器人

问题描述
    永远不要以为Matrix67就是传说中的情圣。很少有人知道，Matrix67竟然不好意思主动向MM表白！为此，Matrix67派出他的表白机器人，帮他完成这一项光荣而艰巨的任务。
    Matrix67和MM所在的地方可以看作是一个封闭的平面空间，里面分成了M x N个房间，某些房间之间可能有墙。Matrix67总在最左下角的那个房间，MM总在最右上角的那个房间。Matrix67需要给它的机器人输入一系列方向指令，控制机器人避开墙壁到达MM所在的位置。如果L表示向左移一格，R表示向右移一格，U表示向上移一格，D表示向下移一格，那么在下图所示的4×4平面地图里，命令序列RURUUR可以让机器人从起点（左下角）到达终点（右上角）。

#—#—#—#—#
|       |     F |
#   #   #   #—#
|       |       |
#   #   #   #—#
|   |           |
#   #   #   #   #
| S             |
#—#—#—#—#

    但问题远远没有这么简单。由于设计上的缺陷，Matrix67的机器人只能记忆K条指令。这就意味着，当机器人的行走路线过长时，指令不一定能完整地输入机器人。这怎么办呢？Matrix67想到一个好办法：如果让机器人反复执行预先给定的K条指令，那么恰当的指令序列也能使机器人到达终点（虽然这样可能会走很多重复的路）。机器人会忽略所有命令它撞墙的指令。也就是说，如果下一个指令对应的方向上是一面墙的话，机器人将跳过该指令。Matrix67希望知道，是否存在一个长度为K的命令序列，若机器人反复执行这段指令，最终会到达MM所在的地方。对于上面给出的例子，当K=4时，RRLU是一个合法的答案。

输入数据
    第一行输入四个用空格隔开的正整数M、N、W和K，表示该平面区域内有M行N列小房间，房间与房间之间共有W面墙，Matrix67需要给机器人输入的指令长度为K。
    以下W行每行四个数Ai, Aj, Bi, Bj，表示第Ai行Aj列的房间与Bi行Bj列的房间之间有一面墙。

输出数据
    你的输出数据应该是一个由L、R、U、D四种字符组成的长度为K的字符串，表示一个合法的指令序列。机器人反复执行这串指令后最终可以到达右上角的房间。
    输入数据保证有唯一解，因此你不用考虑多解或无解的情况。

样例输入
4 4 5 4
1 2 1 3
2 2 2 3
1 4 2 4
2 4 3 4
3 1 3 2

样例输出
RRLU

数据规模
    对于30%的数据，K<=4；
    对于100%的数