Description

假设某外卖平台雇佣了n位“外卖小哥”送外卖。每一天的外卖时间离散化为144个时间段（每5分钟一个时间段，早上10:00到晚上10:00）。
城市交通网：整个城市交通网用三元组G=<V,E,W>表示，其中V={v_1,v_2,…,v_m}表示城市中的m个区域，每一条边e_ij∈E表示区域i到j的无向边。对于每一条边，w_ij表示这两个区域的通行时间（假设所有外卖小哥都用同一种交通工具）。
订单请求：假设提前知道所有的顾客的外卖订单R={r_1,r_2,…,r_k}。每个订单r_j∈R可以用三元组表示(v_j^p,v_j^d,[t_j^e,t_j^l ])，其中v_j^p表示订单r_j的取货区域，v_j^d表示订单r_j的送达区域。每个订单r_j有个灵活的送达窗口[t_j^e,t_j^l]⊆[1,144]，只有在这个时间段内，订单才能送达，其中t_j^e是最早送达时间，t_j^l表示订单最晚送达时间。譬如,[t_j^e,t_j^l]=[16:30,17:00] （输入会换成0~144之间的整数）表示订单只能在下午4:30到5:00之间送达。如果一个订单早于最早时间到达，外卖小哥必须要等到最早时间才能送货。

给定n个外卖小哥，城市交通网G=<V,E,W>，以及订单请求R，假设外卖小哥的交通工具容量有限，不能同时承载两个及以上的订单，即只能将上个外卖送达目的地，才能去取下一个订单。请设计算法为每个外卖小哥制定一个送货顺序，使得能够成功完成的订单数目尽可能的多。

Input

输入：
第一行包含3个正整数n,e,r,x，表示路网的顶点数、边数、总订单数和外卖小哥的人数
接下来的e行，每行包含三个正整数i,j,w，(1 <= i, j <= n)表示从点i到j的无向边，通行时间为w (1≤w≤144)。
接下来的r行，每行包含4个正整数v_p,v_d,t_e,t_l，表示第i(i从1开始)个订单的取货区域、送达区域，最早送达时间，最晚送达时间。

Output

输出
对于每组数据，一共输出x个块，每行开头输出solution i，代表第i个外卖小哥的配送情况。
每组答案用一个或多个空行隔开
每行开头先输出操作类型"pick"（取外卖）、"serve"（送达外卖）、"goto"（在路网中穿行）
pick操作后跟一个正整数i，取第i号外卖；
goto操作后先输出路径中的顶点数目x，再输出路径上的x个节点；
serve操作后跟一个正整数i，表示送达第i号外卖。

注意：
1. 不一定需要安排所有外卖小哥送货，输出Solution i中的i不要重复
2. 如果有结束时没有送完的外卖，可以不用输出serve
3. 图是无向边
4. 每个外卖小哥在时刻0位于取第一单外卖的位置
5. 输入数据量较大，C++可以通过下面三行代码加速iostream读取和输出：
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

Sample Input

1
4 4 2 2
1 2 10
2 3 10
3 4 10
4 1 10
1 3 140 144
2 4 140 144

Sample Output

solution 1
pick 1
goto 3 1 2 3
serve 1
solution 2
pick 2
goto 3 2 3 4
serve 2

说明
对于数据1：
第一个外卖小哥在时刻0取到1号外卖，在时刻20到达点3，等待到时刻140送达
第二个外卖小哥在时刻0取到2号外卖，在时刻20到达点4，等待到时刻140送达