末日时在做什么？有没有空？可以来拯救吗？

我不会再闷闷不乐了

那撕裂胸口的悲伤
还有快流下来的眼泪
全都是塑造出现在的我的东西

烦恼
灰心
痛苦
喜悦
全部不可或缺
现在站在这里的不是别人

毫无疑问是我自己，是珂朵莉
对，至少现在如此

记忆慢慢地缺失
人格在逐渐崩坏
抱歉
你们当中
已经有一半的人我不记得了...
忘记的名字还可以重新记住
但是失去的记忆却无可挽回
这个将要崩坏的自己，还能被称作珂朵莉吗...？

可即便这样的感情，我也想要毫无保留地去珍惜
因为如果连这种感情都失去的时候
我大概就会...彻底消失吧

                                                                           ————世界上最幸福的女孩

夜晚，萤火虫点缀的静谧草坪上，威廉为了满足珂朵莉临走前的些许愿望，将他的圣剑分裂成n块碎片

假设这n块圣剑碎片从左到右编号为1，2，3......n

每块碎片都有一个数值为整数的能量值

当且仅当两块碎片中间的碎片能量值比它们都低时，这两块碎片才能满足珂朵莉的一个愿望(中间没有碎片时假设其能量为0)

现在，你只知道能量最高的碎片是第P块，它的能量是V，剩余碎片的能量未知（可能存在多块碎片能量同时最高）

但是，你还知道这n块碎片中存在着m对关系

每对关系都指明了某两块碎片可以满足珂朵莉的一个愿望

在满足所有这m对关系的情况下，请你输出每块碎片能量的最大值是多少

第一行输入整数 n，P，V，m  ，数据用空格隔开

接下来m行，每行输入两个整数A和B，代表第A和第B块碎片能实现珂朵莉的一个愿望（数据保证A!=B）

数据范围：（1<=P<=n<=10000;1<=V<=1000000;1<=A,B<=n<=10000;0<=m<=10000）

一共输出n行数据，每行输出一个整数

第i行输出的整数代表第i块碎片的最大能量值

9 3 5 5
1 3
5 3
4 3
3 7
9 8

5
4
5
3
4
4
5
5
5