; LLVM IR from tangjz/acm-icpc :: codeforces/complete (796F)

; Unoptimized IR (clang -disable-llvm-passes):
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

%struct.Info = type { i32, i32, i32, i32 }
%class.anon = type { i8 }

@n = external dso_local global i32, align 4
@m = external dso_local global i32, align 4
@upp = external dso_local global [300001 x i32], align 16
@seg = external dso_local global [600003 x i32], align 16
@ord = external dso_local global [300001 x i32], align 16
@que = external dso_local global [300001 x %struct.Info], align 16
@.str = external hidden unnamed_addr constant [5 x i8], align 1
@.str.1 = external hidden unnamed_addr constant [7 x i8], align 1
@.str.2 = external hidden unnamed_addr constant [3 x i8], align 1
@.str.3 = external hidden unnamed_addr constant [3 x i8], align 1
@.str.4 = external hidden unnamed_addr constant [4 x i8], align 1
@.str.5 = external hidden unnamed_addr constant [5 x i8], align 1
@.str.6 = external hidden unnamed_addr constant [3 x i8], align 1

; Function Attrs: mustprogress uwtable
declare dso_local void @_Z7seg_dfsiii(i32 noundef, i32 noundef, i32 noundef) #0

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.start.p0(i64 immarg, ptr nocapture) #1

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture) #1

; Function Attrs: mustprogress uwtable
declare dso_local void @_Z7seg_updiiiiib(i32 noundef, i32 noundef, i32 noundef, i32 noundef, i32 noundef, i1 noundef zeroext) #0

; Function Attrs: mustprogress uwtable
declare dso_local noundef i32 @_Z7seg_queiii(i32 noundef, i32 noundef, i32 noundef) #0

; Function Attrs: mustprogress uwtable
declare dso_local noundef i32 @_Z7seg_queiiii(i32 noundef, i32 noundef, i32 noundef, i32 noundef) #0

; Function Attrs: mustprogress norecurse uwtable
define dso_local noundef i32 @main() #2 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  %3 = alloca ptr, align 8
  %4 = alloca i32, align 4
  %5 = alloca i32, align 4
  %6 = alloca ptr, align 8
  %7 = alloca i32, align 4
  %8 = alloca %class.anon, align 1
  %9 = alloca i32, align 4
  %10 = alloca i32, align 4
  %11 = alloca i32, align 4
  %12 = alloca i32, align 4
  %13 = alloca i32, align 4
  %14 = alloca i32, align 4
  store i32 0, ptr %1, align 4
  %15 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef @.str, ptr noundef @n, ptr noundef @m)
  %16 = load i32, ptr @n, align 4, !tbaa !5
  %17 = sext i32 %16 to i64
  %18 = mul i64 %17, 4
  call void @llvm.memset.p0.i64(ptr align 4 getelementptr inbounds (i32, ptr @upp, i64 1), i8 -1, i64 %18, i1 false)
  %19 = load i32, ptr @n, align 4, !tbaa !5
  %20 = shl i32 %19, 1
  %21 = sext i32 %20 to i64
  %22 = mul i64 %21, 4
  call void @llvm.memset.p0.i64(ptr align 4 getelementptr inbounds (i32, ptr @seg, i64 1), i8 63, i64 %22, i1 false)
  call void @llvm.lifetime.start.p0(i64 4, ptr %2) #6
  store i32 1, ptr %2, align 4, !tbaa !5
  br label %23

23:                                               ; preds = %78, %0
  %24 = load i32, ptr %2, align 4, !tbaa !5
  %25 = load i32, ptr @m, align 4, !tbaa !5
  %26 = icmp sle i32 %24, %25
  br i1 %26, label %28, label %27

27:                                               ; preds = %23
  call void @llvm.lifetime.end.p0(i64 4, ptr %2) #6
  br label %81

28:                                               ; preds = %23
  call void @llvm.lifetime.start.p0(i64 8, ptr %3) #6
  %29 = load i32, ptr %2, align 4, !tbaa !5
  %30 = sext i32 %29 to i64
  %31 = getelementptr inbounds [300001 x %struct.Info], ptr @que, i64 0, i64 %30
  store ptr %31, ptr %3, align 8, !tbaa !9
  %32 = load ptr, ptr %3, align 8, !tbaa !9
  %33 = getelementptr inbounds %struct.Info, ptr %32, i32 0, i32 0
  %34 = load ptr, ptr %3, align 8, !tbaa !9
  %35 = getelementptr inbounds %struct.Info, ptr %34, i32 0, i32 1
  %36 = load ptr, ptr %3, align 8, !tbaa !9
  %37 = getelementptr inbounds %struct.Info, ptr %36, i32 0, i32 2
  %38 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef @.str.1, ptr noundef %33, ptr noundef %35, ptr noundef %37)
  %39 = load ptr, ptr %3, align 8, !tbaa !9
  %40 = getelementptr inbounds %struct.Info, ptr %39, i32 0, i32 0
  %41 = load i32, ptr %40, align 4, !tbaa !11
  %42 = icmp eq i32 %41, 1
  br i1 %42, label %43, label %57

43:                                               ; preds = %28
  %44 = load ptr, ptr %3, align 8, !tbaa !9
  %45 = getelementptr inbounds %struct.Info, ptr %44, i32 0, i32 3
  %46 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef @.str.2, ptr noundef %45)
  %47 = load i32, ptr @n, align 4, !tbaa !5
  %48 = load ptr, ptr %3, align 8, !tbaa !9
  %49 = getelementptr inbounds %struct.Info, ptr %48, i32 0, i32 1
  %50 = load i32, ptr %49, align 4, !tbaa !13
  %51 = load ptr, ptr %3, align 8, !tbaa !9
  %52 = getelementptr inbounds %struct.Info, ptr %51, i32 0, i32 2
  %53 = load i32, ptr %52, align 4, !tbaa !14
  %54 = load ptr, ptr %3, align 8, !tbaa !9
  %55 = getelementptr inbounds %struct.Info, ptr %54, i32 0, i32 3
  %56 = load i32, ptr %55, align 4, !tbaa !15
  call void @_Z7seg_updiiiiib(i32 noundef 1, i32 noundef %47, i32 noundef %50, i32 noundef %53, i32 noundef %56, i1 noundef zeroext false)
  br label %77

57:                                               ; preds = %28
  %58 = load ptr, ptr %3, align 8, !tbaa !9
  %59 = getelementptr inbounds %struct.Info, ptr %58, i32 0, i32 1
  %60 = load i32, ptr %59, align 4, !tbaa !13
  %61 = sext i32 %60 to i64
  %62 = getelementptr inbounds [300001 x i32], ptr @upp, i64 0, i64 %61
  %63 = load i32, ptr %62, align 4, !tbaa !5
  %64 = icmp eq i32 %63, -1
  br i1 %64, label %65, label %76

65:                                               ; preds = %57
  %66 = load i32, ptr @n, align 4, !tbaa !5
  %67 = load ptr, ptr %3, align 8, !tbaa !9
  %68 = getelementptr inbounds %struct.Info, ptr %67, i32 0, i32 1
  %69 = load i32, ptr %68, align 4, !tbaa !13
  %70 = call noundef i32 @_Z7seg_queiii(i32 noundef 1, i32 noundef %66, i32 noundef %69)
  %71 = load ptr, ptr %3, align 8, !tbaa !9
  %72 = getelementptr inbounds %struct.Info, ptr %71, i32 0, i32 1
  %73 = load i32, ptr %72, align 4, !tbaa !13
  %74 = sext i32 %73 to i64
  %75 = getelementptr inbounds [300001 x i32], ptr @upp, i64 0, i64 %74
  store i32 %70, ptr %75, align 4, !tbaa !5
  br label %76

76:                                               ; preds = %65, %57
  br label %77

77:                                               ; preds = %76, %43
  call void @llvm.lifetime.end.p0(i64 8, ptr %3) #6
  br label %78

78:                                               ; preds = %77
  %79 = load i32, ptr %2, align 4, !tbaa !5
  %80 = add nsw i32 %79, 1
  store i32 %80, ptr %2, align 4, !tbaa !5
  br label %23, !llvm.loop !16

81:                                               ; preds = %27
  %82 = load i32, ptr @n, align 4, !tbaa !5
  call void @_Z7seg_dfsiii(i32 noundef 1, i32 noundef %82, i32 noundef 1061109567)
  call void @llvm.lifetime.start.p0(i64 4, ptr %4) #6
  store i32 1, ptr %4, align 4, !tbaa !5
  br label %83

83:                                               ; preds = %127, %81
  %84 = load i32, ptr %4, align 4, !tbaa !5
  %85 = load i32, ptr @m, align 4, !tbaa !5
  %86 = icmp sle i32 %84, %85
  br i1 %86, label %88, label %87

87:                                               ; preds = %83
  store i32 5, ptr %5, align 4
  br label %130

88:                                               ; preds = %83
  call void @llvm.lifetime.start.p0(i64 8, ptr %6) #6
  %89 = load i32, ptr %4, align 4, !tbaa !5
  %90 = sext i32 %89 to i64
  %91 = getelementptr inbounds [300001 x %struct.Info], ptr @que, i64 0, i64 %90
  store ptr %91, ptr %6, align 8, !tbaa !9
  %92 = load ptr, ptr %6, align 8, !tbaa !9
  %93 = getelementptr inbounds %struct.Info, ptr %92, i32 0, i32 0
  %94 = load i32, ptr %93, align 4, !tbaa !11
  %95 = icmp ne i32 %94, 1
  br i1 %95, label %96, label %107

96:                                               ; preds = %88
  %97 = load i32, ptr @n, align 4, !tbaa !5
  %98 = load ptr, ptr %6, align 8, !tbaa !9
  %99 = getelementptr inbounds %struct.Info, ptr %98, i32 0, i32 1
  %100 = load i32, ptr %99, align 4, !tbaa !13
  %101 = load ptr, ptr %6, align 8, !tbaa !9
  %102 = getelementptr inbounds %struct.Info, ptr %101, i32 0, i32 1
  %103 = load i32, ptr %102, align 4, !tbaa !13
  %104 = load ptr, ptr %6, align 8, !tbaa !9
  %105 = getelementptr inbounds %struct.Info, ptr %104, i32 0, i32 2
  %106 = load i32, ptr %105, align 4, !tbaa !14
  call void @_Z7seg_updiiiiib(i32 noundef 1, i32 noundef %97, i32 noundef %100, i32 noundef %103, i32 noundef %106, i1 noundef zeroext true)
  br label %123

107:                                              ; preds = %88
  %108 = load i32, ptr @n, align 4, !tbaa !5
  %109 = load ptr, ptr %6, align 8, !tbaa !9
  %110 = getelementptr inbounds %struct.Info, ptr %109, i32 0, i32 1
  %111 = load i32, ptr %110, align 4, !tbaa !13
  %112 = load ptr, ptr %6, align 8, !tbaa !9
  %113 = getelementptr inbounds %struct.Info, ptr %112, i32 0, i32 2
  %114 = load i32, ptr %113, align 4, !tbaa !14
  %115 = call noundef i32 @_Z7seg_queiiii(i32 noundef 1, i32 noundef %108, i32 noundef %111, i32 noundef %114)
  %116 = load ptr, ptr %6, align 8, !tbaa !9
  %117 = getelementptr inbounds %struct.Info, ptr %116, i32 0, i32 3
  %118 = load i32, ptr %117, align 4, !tbaa !15
  %119 = icmp ne i32 %115, %118
  br i1 %119, label %120, label %122

120:                                              ; preds = %107
  %121 = call i32 @puts(ptr noundef @.str.3)
  store i32 0, ptr %1, align 4
  store i32 1, ptr %5, align 4
  br label %124

122:                                              ; preds = %107
  br label %123

123:                                              ; preds = %122, %96
  store i32 0, ptr %5, align 4
  br label %124

124:                                              ; preds = %123, %120
  call void @llvm.lifetime.end.p0(i64 8, ptr %6) #6
  %125 = load i32, ptr %5, align 4
  switch i32 %125, label %130 [
    i32 0, label %126
  ]

126:                                              ; preds = %124
  br label %127

127:                                              ; preds = %126
  %128 = load i32, ptr %4, align 4, !tbaa !5
  %129 = add nsw i32 %128, 1
  store i32 %129, ptr %4, align 4, !tbaa !5
  br label %83, !llvm.loop !18

130:                                              ; preds = %124, %87
  call void @llvm.lifetime.end.p0(i64 4, ptr %4) #6
  %131 = load i32, ptr %5, align 4
  switch i32 %131, label %278 [
    i32 5, label %132
    i32 1, label %276
  ]

132:                                              ; preds = %130
  call void @llvm.lifetime.start.p0(i64 4, ptr %7) #6
  store i32 1, ptr %7, align 4, !tbaa !5
  br label %133

133:                                              ; preds = %143, %132
  %134 = load i32, ptr %7, align 4, !tbaa !5
  %135 = load i32, ptr @n, align 4, !tbaa !5
  %136 = icmp sle i32 %134, %135
  br i1 %136, label %138, label %137

137:                                              ; preds = %133
  store i32 8, ptr %5, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %7) #6
  br label %146

138:                                              ; preds = %133
  %139 = load i32, ptr %7, align 4, !tbaa !5
  %140 = load i32, ptr %7, align 4, !tbaa !5
  %141 = sext i32 %140 to i64
  %142 = getelementptr inbounds [300001 x i32], ptr @ord, i64 0, i64 %141
  store i32 %139, ptr %142, align 4, !tbaa !5
  br label %143

143:                                              ; preds = %138
  %144 = load i32, ptr %7, align 4, !tbaa !5
  %145 = add nsw i32 %144, 1
  store i32 %145, ptr %7, align 4, !tbaa !5
  br label %133, !llvm.loop !19

146:                                              ; preds = %137
  %147 = load i32, ptr @n, align 4, !tbaa !5
  %148 = sext i32 %147 to i64
  %149 = getelementptr inbounds i32, ptr @ord, i64 %148
  %150 = getelementptr inbounds i32, ptr %149, i64 1
  call void @"_ZSt4sortIPiZ4mainE3$_0EvT_S2_T0_"(ptr noundef getelementptr inbounds (i32, ptr @ord, i64 1), ptr noundef %150)
  call void @llvm.lifetime.start.p0(i64 4, ptr %9) #6
  store i32 0, ptr %9, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %10) #6
  store i32 1, ptr %10, align 4, !tbaa !5
  br label %151

151:                                              ; preds = %251, %146
  %152 = load i32, ptr %10, align 4, !tbaa !5
  %153 = load i32, ptr @n, align 4, !tbaa !5
  %154 = icmp sle i32 %152, %153
  br i1 %154, label %156, label %155

155:                                              ; preds = %151
  store i32 11, ptr %5, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %10) #6
  br label %252

156:                                              ; preds = %151
  call void @llvm.lifetime.start.p0(i64 4, ptr %11) #6
  %157 = load i32, ptr %10, align 4, !tbaa !5
  %158 = sext i32 %157 to i64
  %159 = getelementptr inbounds [300001 x i32], ptr @ord, i64 0, i64 %158
  %160 = load i32, ptr %159, align 4, !tbaa !5
  %161 = sext i32 %160 to i64
  %162 = getelementptr inbounds [300001 x i32], ptr @upp, i64 0, i64 %161
  %163 = load i32, ptr %162, align 4, !tbaa !5
  store i32 %163, ptr %11, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %12) #6
  %164 = load i32, ptr %11, align 4, !tbaa !5
  %165 = icmp slt i32 %164, 1061109567
  br i1 %165, label %166, label %182

166:                                              ; preds = %156
  %167 = load i32, ptr %11, align 4, !tbaa !5
  %168 = load i32, ptr %9, align 4, !tbaa !5
  %169 = or i32 %168, %167
  store i32 %169, ptr %9, align 4, !tbaa !5
  store i32 0, ptr %12, align 4, !tbaa !5
  br label %170

170:                                              ; preds = %177, %166
  %171 = load i32, ptr %12, align 4, !tbaa !5
  %172 = shl i32 %171, 1
  %173 = or i32 %172, 1
  %174 = load i32, ptr %11, align 4, !tbaa !5
  %175 = icmp sle i32 %173, %174
  br i1 %175, label %176, label %181

176:                                              ; preds = %170
  br label %177

177:                                              ; preds = %176
  %178 = load i32, ptr %12, align 4, !tbaa !5
  %179 = shl i32 %178, 1
  %180 = or i32 %179, 1
  store i32 %180, ptr %12, align 4, !tbaa !5
  br label %170, !llvm.loop !20

181:                                              ; preds = %170
  br label %218

182:                                              ; preds = %156
  store i32 0, ptr %12, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %13) #6
  store i32 536870912, ptr %13, align 4, !tbaa !5
  br label %183

183:                                              ; preds = %202, %182
  %184 = load i32, ptr %13, align 4, !tbaa !5
  %185 = icmp ne i32 %184, 0
  br i1 %185, label %187, label %186

186:                                              ; preds = %183
  store i32 16, ptr %5, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %13) #6
  br label %205

187:                                              ; preds = %183
  %188 = load i32, ptr %9, align 4, !tbaa !5
  %189 = load i32, ptr %13, align 4, !tbaa !5
  %190 = and i32 %188, %189
  %191 = icmp ne i32 %190, 0
  br i1 %191, label %201, label %192

192:                                              ; preds = %187
  %193 = load i32, ptr %12, align 4, !tbaa !5
  %194 = load i32, ptr %13, align 4, !tbaa !5
  %195 = or i32 %193, %194
  %196 = icmp sle i32 %195, 1000000000
  br i1 %196, label %197, label %201

197:                                              ; preds = %192
  %198 = load i32, ptr %13, align 4, !tbaa !5
  %199 = load i32, ptr %12, align 4, !tbaa !5
  %200 = or i32 %199, %198
  store i32 %200, ptr %12, align 4, !tbaa !5
  br label %201

201:                                              ; preds = %197, %192, %187
  br label %202

202:                                              ; preds = %201
  %203 = load i32, ptr %13, align 4, !tbaa !5
  %204 = ashr i32 %203, 1
  store i32 %204, ptr %13, align 4, !tbaa !5
  br label %183, !llvm.loop !21

205:                                              ; preds = %186
  %206 = load i32, ptr %12, align 4, !tbaa !5
  %207 = load i32, ptr %10, align 4, !tbaa !5
  %208 = sext i32 %207 to i64
  %209 = getelementptr inbounds [300001 x i32], ptr @ord, i64 0, i64 %208
  %210 = load i32, ptr %209, align 4, !tbaa !5
  %211 = sext i32 %210 to i64
  %212 = getelementptr inbounds [300001 x i32], ptr @upp, i64 0, i64 %211
  store i32 %206, ptr %212, align 4, !tbaa !5
  %213 = load i32, ptr %12, align 4, !tbaa !5
  %214 = load i32, ptr %9, align 4, !tbaa !5
  %215 = or i32 %214, %213
  store i32 %215, ptr %9, align 4, !tbaa !5
  %216 = load i32, ptr %9, align 4, !tbaa !5
  %217 = xor i32 1073741823, %216
  store i32 %217, ptr %12, align 4, !tbaa !5
  br label %218

218:                                              ; preds = %205, %181
  %219 = load i32, ptr %10, align 4, !tbaa !5
  %220 = add nsw i32 %219, 1
  store i32 %220, ptr %10, align 4, !tbaa !5
  br label %221

221:                                              ; preds = %248, %218
  %222 = load i32, ptr %10, align 4, !tbaa !5
  %223 = load i32, ptr @n, align 4, !tbaa !5
  %224 = icmp sle i32 %222, %223
  br i1 %224, label %225, label %235

225:                                              ; preds = %221
  %226 = load i32, ptr %10, align 4, !tbaa !5
  %227 = sext i32 %226 to i64
  %228 = getelementptr inbounds [300001 x i32], ptr @ord, i64 0, i64 %227
  %229 = load i32, ptr %228, align 4, !tbaa !5
  %230 = sext i32 %229 to i64
  %231 = getelementptr inbounds [300001 x i32], ptr @upp, i64 0, i64 %230
  %232 = load i32, ptr %231, align 4, !tbaa !5
  %233 = load i32, ptr %11, align 4, !tbaa !5
  %234 = icmp eq i32 %232, %233
  br label %235

235:                                              ; preds = %225, %221
  %236 = phi i1 [ false, %221 ], [ %234, %225 ]
  br i1 %236, label %237, label %251

237:                                              ; preds = %235
  %238 = load i32, ptr %12, align 4, !tbaa !5
  %239 = load i32, ptr %10, align 4, !tbaa !5
  %240 = sext i32 %239 to i64
  %241 = getelementptr inbounds [300001 x i32], ptr @ord, i64 0, i64 %240
  %242 = load i32, ptr %241, align 4, !tbaa !5
  %243 = sext i32 %242 to i64
  %244 = getelementptr inbounds [300001 x i32], ptr @upp, i64 0, i64 %243
  store i32 %238, ptr %244, align 4, !tbaa !5
  %245 = load i32, ptr %12, align 4, !tbaa !5
  %246 = load i32, ptr %9, align 4, !tbaa !5
  %247 = or i32 %246, %245
  store i32 %247, ptr %9, align 4, !tbaa !5
  br label %248

248:                                              ; preds = %237
  %249 = load i32, ptr %10, align 4, !tbaa !5
  %250 = add nsw i32 %249, 1
  store i32 %250, ptr %10, align 4, !tbaa !5
  br label %221, !llvm.loop !22

251:                                              ; preds = %235
  call void @llvm.lifetime.end.p0(i64 4, ptr %12) #6
  call void @llvm.lifetime.end.p0(i64 4, ptr %11) #6
  br label %151, !llvm.loop !23

252:                                              ; preds = %155
  %253 = call i32 @puts(ptr noundef @.str.4)
  call void @llvm.lifetime.start.p0(i64 4, ptr %14) #6
  store i32 1, ptr %14, align 4, !tbaa !5
  br label %254

254:                                              ; preds = %272, %252
  %255 = load i32, ptr %14, align 4, !tbaa !5
  %256 = load i32, ptr @n, align 4, !tbaa !5
  %257 = icmp sle i32 %255, %256
  br i1 %257, label %259, label %258

258:                                              ; preds = %254
  store i32 22, ptr %5, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %14) #6
  br label %275

259:                                              ; preds = %254
  %260 = load i32, ptr %14, align 4, !tbaa !5
  %261 = sext i32 %260 to i64
  %262 = getelementptr inbounds [300001 x i32], ptr @upp, i64 0, i64 %261
  %263 = load i32, ptr %262, align 4, !tbaa !5
  %264 = load i32, ptr %14, align 4, !tbaa !5
  %265 = load i32, ptr @n, align 4, !tbaa !5
  %266 = icmp eq i32 %264, %265
  %267 = zext i1 %266 to i64
  %268 = getelementptr inbounds [3 x i8], ptr @.str.6, i64 0, i64 %267
  %269 = load i8, ptr %268, align 1, !tbaa !24
  %270 = sext i8 %269 to i32
  %271 = call i32 (ptr, ...) @printf(ptr noundef @.str.5, i32 noundef %263, i32 noundef %270)
  br label %272

272:                                              ; preds = %259
  %273 = load i32, ptr %14, align 4, !tbaa !5
  %274 = add nsw i32 %273, 1
  store i32 %274, ptr %14, align 4, !tbaa !5
  br label %254, !llvm.loop !25

275:                                              ; preds = %258
  store i32 0, ptr %1, align 4
  store i32 1, ptr %5, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %9) #6
  br label %276

276:                                              ; preds = %275, %130
  %277 = load i32, ptr %1, align 4
  ret i32 %277

278:                                              ; preds = %130
  unreachable
}

declare i32 @__isoc99_scanf(ptr noundef, ...) #3

; Function Attrs: nocallback nofree nounwind willreturn memory(argmem: write)
declare void @llvm.memset.p0.i64(ptr nocapture writeonly, i8, i64, i1 immarg) #4

declare i32 @puts(ptr noundef) #3

; Function Attrs: inlinehint mustprogress uwtable
declare hidden void @"_ZSt4sortIPiZ4mainE3$_0EvT_S2_T0_"(ptr noundef, ptr noundef) #5

declare i32 @printf(ptr noundef, ...) #3

attributes #0 = { mustprogress uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
attributes #2 = { mustprogress norecurse uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #3 = { "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #4 = { nocallback nofree nounwind willreturn memory(argmem: write) }
attributes #5 = { inlinehint mustprogress uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #6 = { nounwind }

!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!4}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{!"clang version 19.1.0 (git@github.com:llvm/llvm-project.git a4bf6cd7cfb1a1421ba92bca9d017b49936c55e4)"}
!5 = !{!6, !6, i64 0}
!6 = !{!"int", !7, i64 0}
!7 = !{!"omnipotent char", !8, i64 0}
!8 = !{!"Simple C++ TBAA"}
!9 = !{!10, !10, i64 0}
!10 = !{!"any pointer", !7, i64 0}
!11 = !{!12, !6, i64 0}
!12 = !{!"_ZTS4Info", !6, i64 0, !6, i64 4, !6, i64 8, !6, i64 12}
!13 = !{!12, !6, i64 4}
!14 = !{!12, !6, i64 8}
!15 = !{!12, !6, i64 12}
!16 = distinct !{!16, !17}
!17 = !{!"llvm.loop.mustprogress"}
!18 = distinct !{!18, !17}
!19 = distinct !{!19, !17}
!20 = distinct !{!20, !17}
!21 = distinct !{!21, !17}
!22 = distinct !{!22, !17}
!23 = distinct !{!23, !17}
!24 = !{!7, !7, i64 0}
!25 = distinct !{!25, !17}


; Optimized IR (opt -passes='default<O3>'):
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

%struct.Info = type { i32, i32, i32, i32 }

@n = external dso_local global i32, align 4
@m = external dso_local global i32, align 4
@upp = external dso_local local_unnamed_addr global [300001 x i32], align 16
@seg = external dso_local local_unnamed_addr global [600003 x i32], align 16
@ord = external dso_local global [300001 x i32], align 16
@que = external dso_local global [300001 x %struct.Info], align 16
@.str = external hidden unnamed_addr constant [5 x i8], align 1
@.str.1 = external hidden unnamed_addr constant [7 x i8], align 1
@.str.2 = external hidden unnamed_addr constant [3 x i8], align 1
@.str.3 = external hidden unnamed_addr constant [3 x i8], align 1
@.str.4 = external hidden unnamed_addr constant [4 x i8], align 1
@.str.5 = external hidden unnamed_addr constant [5 x i8], align 1
@.str.6 = external hidden unnamed_addr constant [3 x i8], align 1

; Function Attrs: mustprogress uwtable
declare dso_local void @_Z7seg_dfsiii(i32 noundef, i32 noundef, i32 noundef) local_unnamed_addr #0

; Function Attrs: mustprogress uwtable
declare dso_local void @_Z7seg_updiiiiib(i32 noundef, i32 noundef, i32 noundef, i32 noundef, i32 noundef, i1 noundef zeroext) local_unnamed_addr #0

; Function Attrs: mustprogress uwtable
declare dso_local noundef i32 @_Z7seg_queiii(i32 noundef, i32 noundef, i32 noundef) local_unnamed_addr #0

; Function Attrs: mustprogress uwtable
declare dso_local noundef i32 @_Z7seg_queiiii(i32 noundef, i32 noundef, i32 noundef, i32 noundef) local_unnamed_addr #0

; Function Attrs: mustprogress norecurse uwtable
define dso_local noundef i32 @main() local_unnamed_addr #1 {
  %1 = tail call i32 (ptr, ...) @__isoc99_scanf(ptr noundef nonnull @.str, ptr noundef nonnull @n, ptr noundef nonnull @m)
  %2 = load i32, ptr @n, align 4, !tbaa !5
  %3 = sext i32 %2 to i64
  %4 = shl nsw i64 %3, 2
  tail call void @llvm.memset.p0.i64(ptr nonnull align 4 getelementptr inbounds (i8, ptr @upp, i64 4), i8 -1, i64 %4, i1 false)
  %5 = shl i32 %2, 1
  %6 = sext i32 %5 to i64
  %7 = shl nsw i64 %6, 2
  tail call void @llvm.memset.p0.i64(ptr nonnull align 4 getelementptr inbounds (i8, ptr @seg, i64 4), i8 63, i64 %7, i1 false)
  %8 = load i32, ptr @m, align 4, !tbaa !5
  %.not102 = icmp slt i32 %8, 1
  br i1 %.not102, label %._crit_edge, label %.lr.ph

._crit_edge.loopexit:                             ; preds = %36
  %.pre = load i32, ptr @n, align 4, !tbaa !5
  br label %._crit_edge

._crit_edge:                                      ; preds = %._crit_edge.loopexit, %0
  %9 = phi i32 [ %.pre, %._crit_edge.loopexit ], [ %2, %0 ]
  tail call void @_Z7seg_dfsiii(i32 noundef 1, i32 noundef %9, i32 noundef 1061109567)
  %10 = load i32, ptr @m, align 4, !tbaa !5
  %.not85104 = icmp slt i32 %10, 1
  br i1 %.not85104, label %.preheader101, label %.lr.ph107

.lr.ph:                                           ; preds = %0, %36
  %indvars.iv = phi i64 [ %indvars.iv.next, %36 ], [ 1, %0 ]
  %11 = getelementptr inbounds [300001 x %struct.Info], ptr @que, i64 0, i64 %indvars.iv
  %12 = getelementptr inbounds i8, ptr %11, i64 4
  %13 = getelementptr inbounds i8, ptr %11, i64 8
  %14 = tail call i32 (ptr, ...) @__isoc99_scanf(ptr noundef nonnull @.str.1, ptr noundef nonnull %11, ptr noundef nonnull %12, ptr noundef nonnull %13)
  %15 = load i32, ptr %11, align 16, !tbaa !9
  %16 = icmp eq i32 %15, 1
  br i1 %16, label %17, label %24

17:                                               ; preds = %.lr.ph
  %18 = getelementptr inbounds i8, ptr %11, i64 12
  %19 = tail call i32 (ptr, ...) @__isoc99_scanf(ptr noundef nonnull @.str.2, ptr noundef nonnull %18)
  %20 = load i32, ptr @n, align 4, !tbaa !5
  %21 = load i32, ptr %12, align 4, !tbaa !11
  %22 = load i32, ptr %13, align 8, !tbaa !12
  %23 = load i32, ptr %18, align 4, !tbaa !13
  tail call void @_Z7seg_updiiiiib(i32 noundef 1, i32 noundef %20, i32 noundef %21, i32 noundef %22, i32 noundef %23, i1 noundef zeroext false)
  br label %36

24:                                               ; preds = %.lr.ph
  %25 = load i32, ptr %12, align 4, !tbaa !11
  %26 = sext i32 %25 to i64
  %27 = getelementptr inbounds [300001 x i32], ptr @upp, i64 0, i64 %26
  %28 = load i32, ptr %27, align 4, !tbaa !5
  %29 = icmp eq i32 %28, -1
  br i1 %29, label %30, label %36

30:                                               ; preds = %24
  %31 = load i32, ptr @n, align 4, !tbaa !5
  %32 = tail call noundef i32 @_Z7seg_queiii(i32 noundef 1, i32 noundef %31, i32 noundef %25)
  %33 = load i32, ptr %12, align 4, !tbaa !11
  %34 = sext i32 %33 to i64
  %35 = getelementptr inbounds [300001 x i32], ptr @upp, i64 0, i64 %34
  store i32 %32, ptr %35, align 4, !tbaa !5
  br label %36

36:                                               ; preds = %24, %30, %17
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %37 = load i32, ptr @m, align 4, !tbaa !5
  %38 = sext i32 %37 to i64
  %.not.not = icmp slt i64 %indvars.iv, %38
  br i1 %.not.not, label %.lr.ph, label %._crit_edge.loopexit, !llvm.loop !14

.preheader101:                                    ; preds = %58, %._crit_edge
  %39 = load i32, ptr @n, align 4, !tbaa !5
  %.not88108 = icmp slt i32 %39, 1
  br i1 %.not88108, label %._crit_edge111, label %.lr.ph110.preheader

.lr.ph110.preheader:                              ; preds = %.preheader101
  %40 = add nuw i32 %39, 1
  %wide.trip.count = zext i32 %40 to i64
  %41 = zext nneg i32 %39 to i64
  %min.iters.check = icmp ult i32 %39, 8
  br i1 %min.iters.check, label %.lr.ph110.preheader156, label %vector.ph

.lr.ph110.preheader156:                           ; preds = %middle.block, %.lr.ph110.preheader
  %indvars.iv139.ph = phi i64 [ 1, %.lr.ph110.preheader ], [ %ind.end, %middle.block ]
  br label %.lr.ph110

vector.ph:                                        ; preds = %.lr.ph110.preheader
  %n.vec = and i64 %41, 2147483640
  %ind.end = or disjoint i64 %n.vec, 1
  br label %vector.body

vector.body:                                      ; preds = %vector.body, %vector.ph
  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
  %vec.ind = phi <4 x i32> [ <i32 1, i32 2, i32 3, i32 4>, %vector.ph ], [ %vec.ind.next, %vector.body ]
  %step.add = add <4 x i32> %vec.ind, <i32 4, i32 4, i32 4, i32 4>
  %offset.idx = or disjoint i64 %index, 1
  %42 = getelementptr inbounds [300001 x i32], ptr @ord, i64 0, i64 %offset.idx
  %43 = getelementptr inbounds i8, ptr %42, i64 16
  store <4 x i32> %vec.ind, ptr %42, align 4, !tbaa !5
  store <4 x i32> %step.add, ptr %43, align 4, !tbaa !5
  %index.next = add nuw i64 %index, 8
  %vec.ind.next = add <4 x i32> %vec.ind, <i32 8, i32 8, i32 8, i32 8>
  %44 = icmp eq i64 %index.next, %n.vec
  br i1 %44, label %middle.block, label %vector.body, !llvm.loop !16

middle.block:                                     ; preds = %vector.body
  %cmp.n = icmp eq i64 %n.vec, %41
  br i1 %cmp.n, label %._crit_edge111, label %.lr.ph110.preheader156

.lr.ph107:                                        ; preds = %._crit_edge, %58
  %indvars.iv136 = phi i64 [ %indvars.iv.next137, %58 ], [ 1, %._crit_edge ]
  %45 = getelementptr inbounds [300001 x %struct.Info], ptr @que, i64 0, i64 %indvars.iv136
  %46 = load i32, ptr %45, align 16, !tbaa !9
  %.not86 = icmp eq i32 %46, 1
  %47 = load i32, ptr @n, align 4, !tbaa !5
  %48 = getelementptr inbounds i8, ptr %45, i64 4
  %49 = load i32, ptr %48, align 4, !tbaa !11
  %50 = getelementptr inbounds i8, ptr %45, i64 8
  %51 = load i32, ptr %50, align 8, !tbaa !12
  br i1 %.not86, label %53, label %52

52:                                               ; preds = %.lr.ph107
  tail call void @_Z7seg_updiiiiib(i32 noundef 1, i32 noundef %47, i32 noundef %49, i32 noundef %49, i32 noundef %51, i1 noundef zeroext true)
  br label %58

53:                                               ; preds = %.lr.ph107
  %54 = tail call noundef i32 @_Z7seg_queiiii(i32 noundef 1, i32 noundef %47, i32 noundef %49, i32 noundef %51)
  %55 = getelementptr inbounds i8, ptr %45, i64 12
  %56 = load i32, ptr %55, align 4, !tbaa !13
  %.not87 = icmp eq i32 %54, %56
  br i1 %.not87, label %58, label %.thread

.thread:                                          ; preds = %53
  %57 = tail call i32 @puts(ptr noundef nonnull dereferenceable(1) @.str.3)
  br label %.loopexit

58:                                               ; preds = %53, %52
  %indvars.iv.next137 = add nuw nsw i64 %indvars.iv136, 1
  %59 = load i32, ptr @m, align 4, !tbaa !5
  %60 = sext i32 %59 to i64
  %.not85.not = icmp slt i64 %indvars.iv136, %60
  br i1 %.not85.not, label %.lr.ph107, label %.preheader101, !llvm.loop !19

._crit_edge111:                                   ; preds = %.lr.ph110, %middle.block, %.preheader101
  %61 = sext i32 %39 to i64
  %62 = getelementptr inbounds i32, ptr @ord, i64 %61
  %63 = getelementptr inbounds i8, ptr %62, i64 4
  tail call void @"_ZSt4sortIPiZ4mainE3$_0EvT_S2_T0_"(ptr noundef nonnull getelementptr inbounds (i8, ptr @ord, i64 4), ptr noundef nonnull %63)
  %64 = load i32, ptr @n, align 4, !tbaa !5
  %.not89125 = icmp slt i32 %64, 1
  br i1 %.not89125, label %._crit_edge130, label %.lr.ph129.preheader

.lr.ph129.preheader:                              ; preds = %._crit_edge111
  %65 = add nuw i32 %64, 1
  %narrow = add nuw i32 %64, 1
  %66 = zext i32 %narrow to i64
  br label %.lr.ph129

.lr.ph110:                                        ; preds = %.lr.ph110.preheader156, %.lr.ph110
  %indvars.iv139 = phi i64 [ %indvars.iv.next140, %.lr.ph110 ], [ %indvars.iv139.ph, %.lr.ph110.preheader156 ]
  %67 = getelementptr inbounds [300001 x i32], ptr @ord, i64 0, i64 %indvars.iv139
  %68 = trunc nuw nsw i64 %indvars.iv139 to i32
  store i32 %68, ptr %67, align 4, !tbaa !5
  %indvars.iv.next140 = add nuw nsw i64 %indvars.iv139, 1
  %exitcond.not = icmp eq i64 %indvars.iv.next140, %wide.trip.count
  br i1 %exitcond.not, label %._crit_edge111, label %.lr.ph110, !llvm.loop !20

._crit_edge130:                                   ; preds = %.critedge, %._crit_edge111
  %69 = tail call i32 @puts(ptr noundef nonnull dereferenceable(1) @.str.4)
  %70 = load i32, ptr @n, align 4, !tbaa !5
  %.not90131 = icmp slt i32 %70, 1
  br i1 %.not90131, label %.loopexit, label %.lr.ph134

.lr.ph129:                                        ; preds = %.lr.ph129.preheader, %.critedge
  %.070127 = phi i32 [ %.171.lcssa, %.critedge ], [ 1, %.lr.ph129.preheader ]
  %.072126 = phi i32 [ %.274.lcssa, %.critedge ], [ 0, %.lr.ph129.preheader ]
  %71 = sext i32 %.070127 to i64
  %72 = getelementptr inbounds [300001 x i32], ptr @ord, i64 0, i64 %71
  %73 = load i32, ptr %72, align 4, !tbaa !5
  %74 = sext i32 %73 to i64
  %75 = getelementptr inbounds [300001 x i32], ptr @upp, i64 0, i64 %74
  %76 = load i32, ptr %75, align 4, !tbaa !5
  %77 = icmp slt i32 %76, 1061109567
  br i1 %77, label %.preheader, label %.preheader.preheader

.preheader.preheader:                             ; preds = %.lr.ph129
  %78 = and i32 %.072126, 939524096
  %.2.2 = xor i32 %78, 939524096
  %79 = and i32 %.072126, 67108864
  %.not92.3 = icmp eq i32 %79, 0
  %80 = or disjoint i32 %.2.2, 67108864
  %81 = icmp ult i32 %80, 1000000001
  %82 = select i1 %.not92.3, i1 %81, i1 false
  %.2.3 = select i1 %82, i32 %80, i32 %.2.2
  %83 = and i32 %.072126, 33554432
  %.not92.4 = icmp eq i32 %83, 0
  %84 = or disjoint i32 %.2.3, 33554432
  %85 = icmp ult i32 %84, 1000000001
  %86 = select i1 %.not92.4, i1 %85, i1 false
  %.2.4 = select i1 %86, i32 %84, i32 %.2.3
  %87 = and i32 %.072126, 16777216
  %.not92.5 = icmp eq i32 %87, 0
  %88 = or i32 %.2.4, 16777216
  %89 = icmp ult i32 %88, 1000000001
  %90 = select i1 %.not92.5, i1 %89, i1 false
  %.2.5 = select i1 %90, i32 %88, i32 %.2.4
  %91 = and i32 %.072126, 8388608
  %.not92.6 = icmp eq i32 %91, 0
  %92 = or i32 %.2.5, 8388608
  %93 = icmp ult i32 %92, 1000000001
  %94 = select i1 %.not92.6, i1 %93, i1 false
  %.2.6 = select i1 %94, i32 %92, i32 %.2.5
  %95 = and i32 %.072126, 4194304
  %.not92.7 = icmp eq i32 %95, 0
  %96 = or i32 %.2.6, 4194304
  %97 = icmp ult i32 %96, 1000000001
  %98 = select i1 %.not92.7, i1 %97, i1 false
  %.2.7 = select i1 %98, i32 %96, i32 %.2.6
  %99 = and i32 %.072126, 2097152
  %.not92.8 = icmp eq i32 %99, 0
  %100 = or i32 %.2.7, 2097152
  %101 = icmp ult i32 %100, 1000000001
  %102 = select i1 %.not92.8, i1 %101, i1 false
  %.2.8 = select i1 %102, i32 %100, i32 %.2.7
  %103 = and i32 %.072126, 1048576
  %.not92.9 = icmp eq i32 %103, 0
  %104 = or i32 %.2.8, 1048576
  %105 = icmp ult i32 %104, 1000000001
  %106 = select i1 %.not92.9, i1 %105, i1 false
  %.2.9 = select i1 %106, i32 %104, i32 %.2.8
  %107 = and i32 %.072126, 524288
  %.not92.10 = icmp eq i32 %107, 0
  %108 = or i32 %.2.9, 524288
  %109 = icmp ult i32 %108, 1000000001
  %110 = select i1 %.not92.10, i1 %109, i1 false
  %.2.10 = select i1 %110, i32 %108, i32 %.2.9
  %111 = and i32 %.072126, 262144
  %.not92.11 = icmp eq i32 %111, 0
  %112 = or i32 %.2.10, 262144
  %113 = icmp ult i32 %112, 1000000001
  %114 = select i1 %.not92.11, i1 %113, i1 false
  %.2.11 = select i1 %114, i32 %112, i32 %.2.10
  %115 = and i32 %.072126, 131072
  %.not92.12 = icmp eq i32 %115, 0
  %116 = or i32 %.2.11, 131072
  %117 = icmp ult i32 %116, 1000000001
  %118 = select i1 %.not92.12, i1 %117, i1 false
  %.2.12 = select i1 %118, i32 %116, i32 %.2.11
  %119 = and i32 %.072126, 65536
  %.not92.13 = icmp eq i32 %119, 0
  %120 = or i32 %.2.12, 65536
  %121 = icmp ult i32 %120, 1000000001
  %122 = select i1 %.not92.13, i1 %121, i1 false
  %.2.13 = select i1 %122, i32 %120, i32 %.2.12
  %123 = insertelement <16 x i32> poison, i32 %.072126, i64 0
  %124 = shufflevector <16 x i32> %123, <16 x i32> poison, <16 x i32> zeroinitializer
  %125 = and <16 x i32> %124, <i32 1, i32 2, i32 4, i32 8, i32 16, i32 32, i32 64, i32 128, i32 256, i32 512, i32 1024, i32 2048, i32 4096, i32 8192, i32 16384, i32 32768>
  %126 = or i32 %.2.13, 32768
  %127 = icmp ult i32 %126, 1000000001
  %128 = icmp eq <16 x i32> %125, zeroinitializer
  %129 = extractelement <16 x i1> %128, i64 15
  %130 = select i1 %129, i1 %127, i1 false
  %.2.14 = select i1 %130, i32 %126, i32 %.2.13
  %131 = or i32 %.2.14, 16384
  %132 = icmp ult i32 %131, 1000000001
  %133 = extractelement <16 x i1> %128, i64 14
  %134 = select i1 %133, i1 %132, i1 false
  %.2.15 = select i1 %134, i32 %131, i32 %.2.14
  %135 = or i32 %.2.15, 8192
  %136 = icmp ult i32 %135, 1000000001
  %137 = extractelement <16 x i1> %128, i64 13
  %138 = select i1 %137, i1 %136, i1 false
  %.2.16 = select i1 %138, i32 %135, i32 %.2.15
  %139 = or i32 %.2.16, 4096
  %140 = icmp ult i32 %139, 1000000001
  %141 = extractelement <16 x i1> %128, i64 12
  %142 = select i1 %141, i1 %140, i1 false
  %.2.17 = select i1 %142, i32 %139, i32 %.2.16
  %143 = or i32 %.2.17, 2048
  %144 = icmp ult i32 %143, 1000000001
  %145 = extractelement <16 x i1> %128, i64 11
  %146 = select i1 %145, i1 %144, i1 false
  %.2.18 = select i1 %146, i32 %143, i32 %.2.17
  %147 = or i32 %.2.18, 1024
  %148 = icmp ult i32 %147, 1000000001
  %149 = extractelement <16 x i1> %128, i64 10
  %150 = select i1 %149, i1 %148, i1 false
  %.2.19 = select i1 %150, i32 %147, i32 %.2.18
  %151 = or i32 %.2.19, 512
  %152 = icmp ult i32 %151, 1000000001
  %153 = extractelement <16 x i1> %128, i64 9
  %154 = select i1 %153, i1 %152, i1 false
  %.2.20 = select i1 %154, i32 %151, i32 %.2.19
  %155 = or i32 %.2.20, 256
  %156 = icmp ult i32 %155, 1000000001
  %157 = extractelement <16 x i1> %128, i64 8
  %158 = select i1 %157, i1 %156, i1 false
  %.2.21 = select i1 %158, i32 %155, i32 %.2.20
  %159 = or i32 %.2.21, 128
  %160 = icmp ult i32 %159, 1000000001
  %161 = extractelement <16 x i1> %128, i64 7
  %162 = select i1 %161, i1 %160, i1 false
  %.2.22 = select i1 %162, i32 %159, i32 %.2.21
  %163 = or i32 %.2.22, 64
  %164 = icmp ult i32 %163, 1000000001
  %165 = extractelement <16 x i1> %128, i64 6
  %166 = select i1 %165, i1 %164, i1 false
  %.2.23 = select i1 %166, i32 %163, i32 %.2.22
  %167 = or i32 %.2.23, 32
  %168 = icmp ult i32 %167, 1000000001
  %169 = extractelement <16 x i1> %128, i64 5
  %170 = select i1 %169, i1 %168, i1 false
  %.2.24 = select i1 %170, i32 %167, i32 %.2.23
  %171 = or i32 %.2.24, 16
  %172 = icmp ult i32 %171, 1000000001
  %173 = extractelement <16 x i1> %128, i64 4
  %174 = select i1 %173, i1 %172, i1 false
  %.2.25 = select i1 %174, i32 %171, i32 %.2.24
  %175 = or i32 %.2.25, 8
  %176 = icmp ult i32 %175, 1000000001
  %177 = extractelement <16 x i1> %128, i64 3
  %178 = select i1 %177, i1 %176, i1 false
  %.2.26 = select i1 %178, i32 %175, i32 %.2.25
  %179 = or i32 %.2.26, 4
  %180 = icmp ult i32 %179, 1000000001
  %181 = extractelement <16 x i1> %128, i64 2
  %182 = select i1 %181, i1 %180, i1 false
  %.2.27 = select i1 %182, i32 %179, i32 %.2.26
  %183 = or i32 %.2.27, 2
  %184 = icmp ult i32 %183, 1000000001
  %185 = extractelement <16 x i1> %128, i64 1
  %186 = select i1 %185, i1 %184, i1 false
  %.2.28 = select i1 %186, i32 %183, i32 %.2.27
  %187 = or i32 %.2.28, 1
  %188 = icmp ult i32 %187, 1000000001
  %189 = extractelement <16 x i1> %128, i64 0
  %190 = select i1 %189, i1 %188, i1 false
  %.2.29 = select i1 %190, i32 %187, i32 %.2.28
  store i32 %.2.29, ptr %75, align 4, !tbaa !5
  %191 = or i32 %.2.29, %.072126
  %192 = xor i32 %191, 1073741823
  br label %.loopexit100

.preheader:                                       ; preds = %.lr.ph129, %.preheader
  %.065 = phi i32 [ %194, %.preheader ], [ 0, %.lr.ph129 ]
  %193 = shl i32 %.065, 1
  %.not93.not = icmp slt i32 %193, %76
  %194 = or disjoint i32 %193, 1
  br i1 %.not93.not, label %.preheader, label %.loopexit100.loopexit, !llvm.loop !21

.loopexit100.loopexit:                            ; preds = %.preheader
  %195 = or i32 %76, %.072126
  br label %.loopexit100

.loopexit100:                                     ; preds = %.loopexit100.loopexit, %.preheader.preheader
  %.173 = phi i32 [ %191, %.preheader.preheader ], [ %195, %.loopexit100.loopexit ]
  %.3 = phi i32 [ %192, %.preheader.preheader ], [ %.065, %.loopexit100.loopexit ]
  %.171114 = add nsw i32 %.070127, 1
  %.not94.not115 = icmp slt i32 %.070127, %64
  br i1 %.not94.not115, label %.lr.ph119, label %.critedge

.lr.ph119:                                        ; preds = %.loopexit100
  %196 = or i32 %.3, %.173
  %197 = add nsw i64 %71, 1
  %198 = getelementptr inbounds [300001 x i32], ptr @ord, i64 0, i64 %197
  %199 = load i32, ptr %198, align 4, !tbaa !5
  %200 = sext i32 %199 to i64
  %201 = getelementptr inbounds [300001 x i32], ptr @upp, i64 0, i64 %200
  %202 = load i32, ptr %201, align 4, !tbaa !5
  %203 = icmp eq i32 %202, %76
  %204 = trunc nsw i64 %197 to i32
  br i1 %203, label %205, label %.critedge

205:                                              ; preds = %.lr.ph119
  store i32 %.3, ptr %201, align 4, !tbaa !5
  %indvars.iv.next143.peel = add nsw i64 %71, 2
  %exitcond145.peel.not = icmp eq i64 %indvars.iv.next143.peel, %66
  br i1 %exitcond145.peel.not, label %.critedge, label %.peel.next

.peel.next:                                       ; preds = %205, %212
  %indvars.iv142 = phi i64 [ %indvars.iv.next143, %212 ], [ %indvars.iv.next143.peel, %205 ]
  %206 = getelementptr inbounds [300001 x i32], ptr @ord, i64 0, i64 %indvars.iv142
  %207 = load i32, ptr %206, align 4, !tbaa !5
  %208 = sext i32 %207 to i64
  %209 = getelementptr inbounds [300001 x i32], ptr @upp, i64 0, i64 %208
  %210 = load i32, ptr %209, align 4, !tbaa !5
  %211 = icmp eq i32 %210, %76
  br i1 %211, label %212, label %.critedge.loopexit.split.loop.exit150

212:                                              ; preds = %.peel.next
  store i32 %.3, ptr %209, align 4, !tbaa !5
  %indvars.iv.next143 = add nsw i64 %indvars.iv142, 1
  %exitcond145.not = icmp eq i64 %indvars.iv.next143, %66
  br i1 %exitcond145.not, label %.critedge, label %.peel.next, !llvm.loop !22

.critedge.loopexit.split.loop.exit150:            ; preds = %.peel.next
  %213 = trunc nsw i64 %indvars.iv142 to i32
  br label %.critedge

.critedge:                                        ; preds = %212, %.critedge.loopexit.split.loop.exit150, %.lr.ph119, %205, %.loopexit100
  %.274.lcssa = phi i32 [ %.173, %.loopexit100 ], [ %.173, %.lr.ph119 ], [ %196, %205 ], [ %196, %.critedge.loopexit.split.loop.exit150 ], [ %196, %212 ]
  %.171.lcssa = phi i32 [ %.171114, %.loopexit100 ], [ %204, %.lr.ph119 ], [ %65, %205 ], [ %213, %.critedge.loopexit.split.loop.exit150 ], [ %65, %212 ]
  %.not89 = icmp sgt i32 %.171.lcssa, %64
  br i1 %.not89, label %._crit_edge130, label %.lr.ph129, !llvm.loop !24

.lr.ph134:                                        ; preds = %._crit_edge130, %.lr.ph134
  %indvars.iv147 = phi i64 [ %indvars.iv.next148, %.lr.ph134 ], [ 1, %._crit_edge130 ]
  %214 = phi i32 [ %224, %.lr.ph134 ], [ %70, %._crit_edge130 ]
  %215 = getelementptr inbounds [300001 x i32], ptr @upp, i64 0, i64 %indvars.iv147
  %216 = load i32, ptr %215, align 4, !tbaa !5
  %217 = zext i32 %214 to i64
  %218 = icmp eq i64 %indvars.iv147, %217
  %219 = zext i1 %218 to i64
  %220 = getelementptr inbounds [3 x i8], ptr @.str.6, i64 0, i64 %219
  %221 = load i8, ptr %220, align 1, !tbaa !25
  %222 = sext i8 %221 to i32
  %223 = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str.5, i32 noundef %216, i32 noundef %222)
  %indvars.iv.next148 = add nuw nsw i64 %indvars.iv147, 1
  %224 = load i32, ptr @n, align 4, !tbaa !5
  %225 = sext i32 %224 to i64
  %.not90.not = icmp slt i64 %indvars.iv147, %225
  br i1 %.not90.not, label %.lr.ph134, label %.loopexit, !llvm.loop !26

.loopexit:                                        ; preds = %.lr.ph134, %._crit_edge130, %.thread
  ret i32 0
}

; Function Attrs: nofree nounwind
declare noundef i32 @__isoc99_scanf(ptr nocapture noundef readonly, ...) local_unnamed_addr #2

; Function Attrs: mustprogress nocallback nofree nounwind willreturn memory(argmem: write)
declare void @llvm.memset.p0.i64(ptr nocapture writeonly, i8, i64, i1 immarg) #3

; Function Attrs: nofree nounwind
declare noundef i32 @puts(ptr nocapture noundef readonly) local_unnamed_addr #2

; Function Attrs: inlinehint mustprogress uwtable
declare hidden void @"_ZSt4sortIPiZ4mainE3$_0EvT_S2_T0_"(ptr noundef, ptr noundef) local_unnamed_addr #4

; Function Attrs: nofree nounwind
declare noundef i32 @printf(ptr nocapture noundef readonly, ...) local_unnamed_addr #2

attributes #0 = { mustprogress uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { mustprogress norecurse uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #2 = { nofree nounwind "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #3 = { mustprogress nocallback nofree nounwind willreturn memory(argmem: write) }
attributes #4 = { inlinehint mustprogress uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!4}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{!"clang version 19.1.0 (git@github.com:llvm/llvm-project.git a4bf6cd7cfb1a1421ba92bca9d017b49936c55e4)"}
!5 = !{!6, !6, i64 0}
!6 = !{!"int", !7, i64 0}
!7 = !{!"omnipotent char", !8, i64 0}
!8 = !{!"Simple C++ TBAA"}
!9 = !{!10, !6, i64 0}
!10 = !{!"_ZTS4Info", !6, i64 0, !6, i64 4, !6, i64 8, !6, i64 12}
!11 = !{!10, !6, i64 4}
!12 = !{!10, !6, i64 8}
!13 = !{!10, !6, i64 12}
!14 = distinct !{!14, !15}
!15 = !{!"llvm.loop.mustprogress"}
!16 = distinct !{!16, !15, !17, !18}
!17 = !{!"llvm.loop.isvectorized", i32 1}
!18 = !{!"llvm.loop.unroll.runtime.disable"}
!19 = distinct !{!19, !15}
!20 = distinct !{!20, !15, !18, !17}
!21 = distinct !{!21, !15}
!22 = distinct !{!22, !15, !23}
!23 = !{!"llvm.loop.peeled.count", i32 1}
!24 = distinct !{!24, !15}
!25 = !{!7, !7, i64 0}
!26 = distinct !{!26, !15}


; Effective O3 passes: CorrelatedValuePropagationPass,EarlyCSEPass,GVNPass,GlobalOptPass,IPSCCPPass,IndVarSimplifyPass,InferAlignmentPass,InferFunctionAttrsPass,InstCombinePass,InstSimplifyPass,JumpThreadingPass,LCSSAPass,LICMPass,LoopFullUnrollPass,LoopInstSimplifyPass,LoopLoadEliminationPass,LoopRotatePass,LoopSimplifyPass,LoopUnrollPass,LoopVectorizePass,ReassociatePass,SLPVectorizerPass,SROAPass,SimplifyCFGPass,TailCallElimPass