【题目描述】
Rick和他的同事制作了一种新的放射性配方,很多坏人都跟着他们。所以Rick想要在坏人抓住他们之前将他的遗产交给Morty。他们的宇宙中有$n$个行星从$1$到$n$编号。Rick在行星编号$s$(地球),他不知道Morty在哪里。众所周知,里克拥有一支门卫枪。有了这把枪,他就可以打开从他所在行星到任何其他星球(包括那个星球)的单向门。但这支枪有一些限制,因为他仍在使用免费试用版。

默认情况下,他不能用这把枪打开任何门。网站上有q个这些枪支的商品。每次购买时,您只能使用一次,但如果您想再使用它,可以再次购买。网站上的出售的枪有三种类型:

1.通过这种类型的枪,您可以打开从行星$v$到行星$u$的门户。

2.通过这种类型的枪,您可以打开从行星$v$到任何行星的入口,其范围为$[l,r]$。

3.通过这种类型的枪,您可以从任何行星打开门,其索引范围为$[l,r]$到行星$v$。

Rick不知道Morty在哪里,但Unity会告诉他,他希望在他找到并立即开始他的旅程时做好准备。因此,对于每个行星(包括地球本身),他想知道从地球到这个星球所需的最低金额。

【输入格式】
第一行包含三个整数$n,q,s(1\leq

评论