题目背景

小 L 喜欢在图上行走，尤其喜欢走出一条最长路。

题目描述

他给你一张 $n$ 个节点 $m$ 条边的有向且边带权的图和一个整数 $s$，请你 $\forall 1 \leq t \leq n$，求出 $s \to t$ 的按位或最长路。

输入格式

第一行，三个整数 $n, m, s$；

接下来 $m$ 行，每行三个整数 $u, v, w$，表示一条有向边。

输出格式

一行，$n$ 个整数，当不存在一条从 $s$ 到 $i$ 的路径，第 $i$ 个整数为 $-1$；否则，第 $i$ 个整数为 $s \to i$ 的按位或最长路。

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

0 1 3 3 15 15 15 15 -1 -1

样例 #1 解释

该样例对应的图如上。以下为构造从 $1$ 到每个点的按位或最长路的方案之一：

• $1$：$1$。
• $2$：$1 \to 2$。
• $3$：$1 \to 2 \to 3$。
• $4$：$1 \to 2 \to 4$。
• $5$：$1 \to 2 \to 4 \to 5 \to 6 \to 7 \to 5$。
• $6$：$1 \to 2 \to 4 \to 6 \to 7 \to 5 \to 6$。
• $7$：$1 \to 2 \to 4 \to 6 \to 7$。
• $8$：$1 \to 2 \to 4 \to 6 \to 7 \to 8$。
• $9$：不存在一条从 $1$ 到 $9$ 的有向路径。
• $10$：不存在一条从 $1$ 到 $10$ 的有向路径。

数据范围

本题开启捆绑测试。

对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^4$，$0 \leq m \leq 3 \times 10^5$，$1 \leq s, u, v \leq n$，$0 \leq w < 2^{13}$。