Nasarallah is trapped in a hostile labyrinth guarded by robots. The labyrinth is represented as an N x M grid, where:

Empty Cells (.) represent areas Nasarallah can walk through. Walls (#) block movement. Guards (G) patrol specific paths. Escape Portals (E) teleport Nasarallah to another pre-defined portal. Nasarallah starts at a specific cell S and must reach a target cell T. However, the guards make the labyrinth dangerous, and portals introduce complexity.

Rules:

Nasarallah can move up, down, left, or right. Guards patrol in predefined loops (specified in input). If Nasarallah enters a cell at the same moment a guard is present, he is caught. Portals teleport Nasarallah instantly but may have limited uses (e.g., at most K times per portal). Energy Constraint: Each move consumes energy, and Nasarallah only has a limited amount E. Input Format:

N, M: Dimensions of the labyrinth. S_x, S_y: Starting coordinates. T_x, T_y: Target coordinates. P: Number of portals. For each portal, P_x, P_y, Q_x, Q_y, K (portal at (P_x, P_y) leads to (Q_x, Q_y) and can be used K times). G: Number of guards. For each guard, G_x, G_y: Initial position and L: Length of patrol loop. L integers describing movement directions (U, D, L, R). Labyrinth layout: N strings of length M, consisting of '.', '#', 'S', 'T', 'E', 'G'. Output: Print the minimum energy required for Nasarallah to escape. If escape is impossible, print -1.

Constraints:

2 <= N, M <= 1000 1 <= P, G <= 100 1 <= E <= 10^6