游园会总指挥

题目描述

给定 n 种奖品数量、m 个活动周期、允许的礼包数闭区间 [low,high] 和时间上限 T。选择区间内最大的礼包数 d，使每种奖品都能平均分入 d 个相同礼包且没有剩余；再求全部活动的共同周期 P，并统计 [1,T] 中共同发生的次数。

输入格式

第一行输入 n、m、low、high、T，满足 2≤n,m≤100、1≤low≤high≤10^9、1≤T≤10^18。第二行输入 n 个 1 到 10^9 之间的奖品数量；第三行输入 m 个 1 到 10^9 之间的周期。数据保证全部周期的最小公倍数不超过 10^18。

输出格式

若不存在可行 d，仅输出一行 -1。否则第一行输出最大的可行 d；第二行按输入顺序输出每包各类奖品数量；第三行输出两个整数 P 和 ⌊T÷P⌋，分别表示共同周期与不超过 T 的正共同发生次数。

样例

输入

3 3 10 30 500
84 126 210
4 6 10

输出

21
4 6 10
60 8