; LLVM IR from tangjz/acm-icpc :: codeforces/gym/101064E.ll (Z5solvev)

; 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"

%"class.std::vector" = type { %"struct.std::_Vector_base" }
%"struct.std::_Vector_base" = type { %"struct.std::_Vector_base<std::pair<int, char>, std::allocator<std::pair<int, char>>>::_Vector_impl" }
%"struct.std::_Vector_base<std::pair<int, char>, std::allocator<std::pair<int, char>>>::_Vector_impl" = type { %"struct.std::_Vector_base<std::pair<int, char>, std::allocator<std::pair<int, char>>>::_Vector_impl_data" }
%"struct.std::_Vector_base<std::pair<int, char>, std::allocator<std::pair<int, char>>>::_Vector_impl_data" = type { ptr, ptr, ptr }
%"struct.std::pair" = type <{ i32, i8, [3 x i8] }>
%"class.__gnu_cxx::__normal_iterator" = type { ptr }
%"class.__gnu_cxx::__normal_iterator.0" = type { ptr }
%class.anon = type { i8 }

@tot = external dso_local global i32, align 4
@msk = external dso_local global [301 x i32], align 16
@sub = external dso_local global [301 x [11 x i32]], align 16
@f = external dso_local global [301 x i32], align 16
@nxt = external dso_local global [301 x [11 x i32]], align 16
@e = external dso_local global [301 x %"class.std::vector"], align 16
@que = external dso_local global [10000001 x i32], align 16
@dis = external dso_local global [10000001 x i32], align 16
@pre = external dso_local global [10000001 x %"struct.std::pair"], align 16
@_ZZ5solvevE3buf = external hidden global [301 x i8], align 16
@.str = external hidden unnamed_addr constant [5 x i8], align 1
@.str.3 = external hidden unnamed_addr constant [3 x i8], align 1
@_ZZ5solvevE3out = external hidden global [4517 x i8], align 16
@.str.4 = external hidden unnamed_addr constant [2 x i8], align 1

; Function Attrs: mustprogress uwtable
define dso_local void @_Z5solvev() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  %5 = alloca i32, align 4
  %6 = alloca i32, align 4
  %7 = alloca i32, align 4
  %8 = alloca i32, align 4
  %9 = alloca i32, align 4
  %10 = alloca i32, align 4
  %11 = alloca i32, align 4
  %12 = alloca i32, align 4
  %13 = alloca %"struct.std::pair", align 4
  %14 = alloca i32, align 4
  %15 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %16 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %17 = alloca %"class.__gnu_cxx::__normal_iterator.0", align 8
  %18 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %19 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %20 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %21 = alloca %class.anon, align 1
  %22 = alloca %"class.__gnu_cxx::__normal_iterator.0", align 8
  %23 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %24 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %25 = alloca i32, align 4
  %26 = alloca i32, align 4
  %27 = alloca i32, align 4
  %28 = alloca i32, align 4
  %29 = alloca i32, align 4
  %30 = alloca i32, align 4
  %31 = alloca ptr, align 8
  %32 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %33 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %34 = alloca ptr, align 8
  %35 = alloca i32, align 4
  %36 = alloca i32, align 4
  %37 = alloca i32, align 4
  %38 = alloca %"struct.std::pair", align 4
  %39 = alloca i32, align 4
  call void @llvm.lifetime.start.p0(i64 4, ptr %1) #8
  call void @llvm.lifetime.start.p0(i64 4, ptr %2) #8
  %40 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef @.str, ptr noundef %1, ptr noundef %2)
  store i32 0, ptr @tot, align 4, !tbaa !5
  %41 = call noundef i32 @_Z7newNodev()
  call void @llvm.lifetime.start.p0(i64 4, ptr %3) #8
  store i32 0, ptr %3, align 4, !tbaa !5
  br label %42

42:                                               ; preds = %100, %0
  %43 = load i32, ptr %3, align 4, !tbaa !5
  %44 = load i32, ptr %1, align 4, !tbaa !5
  %45 = load i32, ptr %2, align 4, !tbaa !5
  %46 = add nsw i32 %44, %45
  %47 = icmp slt i32 %43, %46
  br i1 %47, label %49, label %48

48:                                               ; preds = %42
  store i32 2, ptr %4, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %3) #8
  br label %103

49:                                               ; preds = %42
  %50 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef @.str.3, ptr noundef @_ZZ5solvevE3buf)
  call void @llvm.lifetime.start.p0(i64 4, ptr %5) #8
  store i32 0, ptr %5, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %6) #8
  store i32 0, ptr %6, align 4, !tbaa !5
  br label %51

51:                                               ; preds = %89, %49
  %52 = load i32, ptr %6, align 4, !tbaa !5
  %53 = sext i32 %52 to i64
  %54 = getelementptr inbounds [301 x i8], ptr @_ZZ5solvevE3buf, i64 0, i64 %53
  %55 = load i8, ptr %54, align 1, !tbaa !9
  %56 = icmp ne i8 %55, 0
  br i1 %56, label %58, label %57

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

58:                                               ; preds = %51
  call void @llvm.lifetime.start.p0(i64 4, ptr %7) #8
  %59 = load i32, ptr %6, align 4, !tbaa !5
  %60 = sext i32 %59 to i64
  %61 = getelementptr inbounds [301 x i8], ptr @_ZZ5solvevE3buf, i64 0, i64 %60
  %62 = load i8, ptr %61, align 1, !tbaa !9
  %63 = sext i8 %62 to i32
  %64 = sub nsw i32 %63, 97
  store i32 %64, ptr %7, align 4, !tbaa !5
  %65 = load i32, ptr %5, align 4, !tbaa !5
  %66 = sext i32 %65 to i64
  %67 = getelementptr inbounds [301 x [11 x i32]], ptr @sub, i64 0, i64 %66
  %68 = load i32, ptr %7, align 4, !tbaa !5
  %69 = sext i32 %68 to i64
  %70 = getelementptr inbounds [11 x i32], ptr %67, i64 0, i64 %69
  %71 = load i32, ptr %70, align 4, !tbaa !5
  %72 = icmp ne i32 %71, 0
  br i1 %72, label %81, label %73

73:                                               ; preds = %58
  %74 = call noundef i32 @_Z7newNodev()
  %75 = load i32, ptr %5, align 4, !tbaa !5
  %76 = sext i32 %75 to i64
  %77 = getelementptr inbounds [301 x [11 x i32]], ptr @sub, i64 0, i64 %76
  %78 = load i32, ptr %7, align 4, !tbaa !5
  %79 = sext i32 %78 to i64
  %80 = getelementptr inbounds [11 x i32], ptr %77, i64 0, i64 %79
  store i32 %74, ptr %80, align 4, !tbaa !5
  br label %81

81:                                               ; preds = %73, %58
  %82 = load i32, ptr %5, align 4, !tbaa !5
  %83 = sext i32 %82 to i64
  %84 = getelementptr inbounds [301 x [11 x i32]], ptr @sub, i64 0, i64 %83
  %85 = load i32, ptr %7, align 4, !tbaa !5
  %86 = sext i32 %85 to i64
  %87 = getelementptr inbounds [11 x i32], ptr %84, i64 0, i64 %86
  %88 = load i32, ptr %87, align 4, !tbaa !5
  store i32 %88, ptr %5, align 4, !tbaa !5
  call void @llvm.lifetime.end.p0(i64 4, ptr %7) #8
  br label %89

89:                                               ; preds = %81
  %90 = load i32, ptr %6, align 4, !tbaa !5
  %91 = add nsw i32 %90, 1
  store i32 %91, ptr %6, align 4, !tbaa !5
  br label %51, !llvm.loop !10

92:                                               ; preds = %57
  %93 = load i32, ptr %3, align 4, !tbaa !5
  %94 = shl i32 1, %93
  %95 = load i32, ptr %5, align 4, !tbaa !5
  %96 = sext i32 %95 to i64
  %97 = getelementptr inbounds [301 x i32], ptr @msk, i64 0, i64 %96
  %98 = load i32, ptr %97, align 4, !tbaa !5
  %99 = or i32 %98, %94
  store i32 %99, ptr %97, align 4, !tbaa !5
  call void @llvm.lifetime.end.p0(i64 4, ptr %5) #8
  br label %100

100:                                              ; preds = %92
  %101 = load i32, ptr %3, align 4, !tbaa !5
  %102 = add nsw i32 %101, 1
  store i32 %102, ptr %3, align 4, !tbaa !5
  br label %42, !llvm.loop !12

103:                                              ; preds = %48
  store i32 0, ptr @que, align 16, !tbaa !5
  store i32 0, ptr @f, align 16, !tbaa !5
  call void @llvm.memcpy.p0.p0.i64(ptr align 16 @nxt, ptr align 16 @sub, i64 40, i1 false)
  call void @llvm.lifetime.start.p0(i64 4, ptr %8) #8
  store i32 0, ptr %8, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %9) #8
  store i32 1, ptr %9, align 4, !tbaa !5
  br label %104

104:                                              ; preds = %256, %103
  %105 = load i32, ptr %8, align 4, !tbaa !5
  %106 = load i32, ptr %9, align 4, !tbaa !5
  %107 = icmp slt i32 %105, %106
  br i1 %107, label %109, label %108

108:                                              ; preds = %104
  store i32 8, ptr %4, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %9) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %8) #8
  br label %259

109:                                              ; preds = %104
  call void @llvm.lifetime.start.p0(i64 4, ptr %10) #8
  %110 = load i32, ptr %8, align 4, !tbaa !5
  %111 = sext i32 %110 to i64
  %112 = getelementptr inbounds [10000001 x i32], ptr @que, i64 0, i64 %111
  %113 = load i32, ptr %112, align 4, !tbaa !5
  store i32 %113, ptr %10, align 4, !tbaa !5
  %114 = load i32, ptr %10, align 4, !tbaa !5
  %115 = sext i32 %114 to i64
  %116 = getelementptr inbounds [301 x %"class.std::vector"], ptr @e, i64 0, i64 %115
  call void @_ZNSt6vectorISt4pairIicESaIS1_EE6resizeEm(ptr noundef nonnull align 8 dereferenceable(24) %116, i64 noundef 10)
  call void @llvm.lifetime.start.p0(i64 4, ptr %11) #8
  store i32 0, ptr %11, align 4, !tbaa !5
  br label %117

117:                                              ; preds = %208, %109
  %118 = load i32, ptr %11, align 4, !tbaa !5
  %119 = icmp slt i32 %118, 10
  br i1 %119, label %121, label %120

120:                                              ; preds = %117
  store i32 11, ptr %4, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %11) #8
  br label %211

121:                                              ; preds = %117
  call void @llvm.lifetime.start.p0(i64 4, ptr %12) #8
  %122 = load i32, ptr %10, align 4, !tbaa !5
  %123 = sext i32 %122 to i64
  %124 = getelementptr inbounds [301 x [11 x i32]], ptr @sub, i64 0, i64 %123
  %125 = load i32, ptr %11, align 4, !tbaa !5
  %126 = sext i32 %125 to i64
  %127 = getelementptr inbounds [11 x i32], ptr %124, i64 0, i64 %126
  %128 = load i32, ptr %127, align 4, !tbaa !5
  store i32 %128, ptr %12, align 4, !tbaa !5
  %129 = load i32, ptr %12, align 4, !tbaa !5
  %130 = icmp ne i32 %129, 0
  br i1 %130, label %148, label %131

131:                                              ; preds = %121
  %132 = load i32, ptr %10, align 4, !tbaa !5
  %133 = sext i32 %132 to i64
  %134 = getelementptr inbounds [301 x i32], ptr @f, i64 0, i64 %133
  %135 = load i32, ptr %134, align 4, !tbaa !5
  %136 = sext i32 %135 to i64
  %137 = getelementptr inbounds [301 x [11 x i32]], ptr @nxt, i64 0, i64 %136
  %138 = load i32, ptr %11, align 4, !tbaa !5
  %139 = sext i32 %138 to i64
  %140 = getelementptr inbounds [11 x i32], ptr %137, i64 0, i64 %139
  %141 = load i32, ptr %140, align 4, !tbaa !5
  %142 = load i32, ptr %10, align 4, !tbaa !5
  %143 = sext i32 %142 to i64
  %144 = getelementptr inbounds [301 x [11 x i32]], ptr @nxt, i64 0, i64 %143
  %145 = load i32, ptr %11, align 4, !tbaa !5
  %146 = sext i32 %145 to i64
  %147 = getelementptr inbounds [11 x i32], ptr %144, i64 0, i64 %146
  store i32 %141, ptr %147, align 4, !tbaa !5
  br label %192

148:                                              ; preds = %121
  %149 = load i32, ptr %10, align 4, !tbaa !5
  %150 = icmp ne i32 %149, 0
  br i1 %150, label %151, label %162

151:                                              ; preds = %148
  %152 = load i32, ptr %10, align 4, !tbaa !5
  %153 = sext i32 %152 to i64
  %154 = getelementptr inbounds [301 x i32], ptr @f, i64 0, i64 %153
  %155 = load i32, ptr %154, align 4, !tbaa !5
  %156 = sext i32 %155 to i64
  %157 = getelementptr inbounds [301 x [11 x i32]], ptr @nxt, i64 0, i64 %156
  %158 = load i32, ptr %11, align 4, !tbaa !5
  %159 = sext i32 %158 to i64
  %160 = getelementptr inbounds [11 x i32], ptr %157, i64 0, i64 %159
  %161 = load i32, ptr %160, align 4, !tbaa !5
  br label %163

162:                                              ; preds = %148
  br label %163

163:                                              ; preds = %162, %151
  %164 = phi i32 [ %161, %151 ], [ 0, %162 ]
  %165 = load i32, ptr %12, align 4, !tbaa !5
  %166 = sext i32 %165 to i64
  %167 = getelementptr inbounds [301 x i32], ptr @f, i64 0, i64 %166
  store i32 %164, ptr %167, align 4, !tbaa !5
  %168 = load i32, ptr %12, align 4, !tbaa !5
  %169 = sext i32 %168 to i64
  %170 = getelementptr inbounds [301 x i32], ptr @f, i64 0, i64 %169
  %171 = load i32, ptr %170, align 4, !tbaa !5
  %172 = sext i32 %171 to i64
  %173 = getelementptr inbounds [301 x i32], ptr @msk, i64 0, i64 %172
  %174 = load i32, ptr %173, align 4, !tbaa !5
  %175 = load i32, ptr %12, align 4, !tbaa !5
  %176 = sext i32 %175 to i64
  %177 = getelementptr inbounds [301 x i32], ptr @msk, i64 0, i64 %176
  %178 = load i32, ptr %177, align 4, !tbaa !5
  %179 = or i32 %178, %174
  store i32 %179, ptr %177, align 4, !tbaa !5
  %180 = load i32, ptr %12, align 4, !tbaa !5
  %181 = load i32, ptr %10, align 4, !tbaa !5
  %182 = sext i32 %181 to i64
  %183 = getelementptr inbounds [301 x [11 x i32]], ptr @nxt, i64 0, i64 %182
  %184 = load i32, ptr %11, align 4, !tbaa !5
  %185 = sext i32 %184 to i64
  %186 = getelementptr inbounds [11 x i32], ptr %183, i64 0, i64 %185
  store i32 %180, ptr %186, align 4, !tbaa !5
  %187 = load i32, ptr %12, align 4, !tbaa !5
  %188 = load i32, ptr %9, align 4, !tbaa !5
  %189 = add nsw i32 %188, 1
  store i32 %189, ptr %9, align 4, !tbaa !5
  %190 = sext i32 %188 to i64
  %191 = getelementptr inbounds [10000001 x i32], ptr @que, i64 0, i64 %190
  store i32 %187, ptr %191, align 4, !tbaa !5
  br label %192

192:                                              ; preds = %163, %131
  call void @llvm.lifetime.start.p0(i64 8, ptr %13) #8
  %193 = load i32, ptr %10, align 4, !tbaa !5
  %194 = sext i32 %193 to i64
  %195 = getelementptr inbounds [301 x [11 x i32]], ptr @nxt, i64 0, i64 %194
  %196 = load i32, ptr %11, align 4, !tbaa !5
  %197 = sext i32 %196 to i64
  %198 = getelementptr inbounds [11 x i32], ptr %195, i64 0, i64 %197
  call void @llvm.lifetime.start.p0(i64 4, ptr %14) #8
  %199 = load i32, ptr %11, align 4, !tbaa !5
  %200 = add nsw i32 97, %199
  store i32 %200, ptr %14, align 4, !tbaa !5
  call void @_ZNSt4pairIicEC2IRiiTnNSt9enable_ifIXaaclsr5_PCCPE22_MoveConstructiblePairIT_T0_EEclsr5_PCCPE30_ImplicitlyMoveConvertiblePairIS4_S5_EEEbE4typeELb1EEEOS4_OS5_(ptr noundef nonnull align 4 dereferenceable(5) %13, ptr noundef nonnull align 4 dereferenceable(4) %198, ptr noundef nonnull align 4 dereferenceable(4) %14)
  %201 = load i32, ptr %10, align 4, !tbaa !5
  %202 = sext i32 %201 to i64
  %203 = getelementptr inbounds [301 x %"class.std::vector"], ptr @e, i64 0, i64 %202
  %204 = load i32, ptr %11, align 4, !tbaa !5
  %205 = sext i32 %204 to i64
  %206 = call noundef nonnull align 4 dereferenceable(5) ptr @_ZNSt6vectorISt4pairIicESaIS1_EEixEm(ptr noundef nonnull align 8 dereferenceable(24) %203, i64 noundef %205) #8
  %207 = call noundef nonnull align 4 dereferenceable(5) ptr @_ZNSt4pairIicEaSEOS0_(ptr noundef nonnull align 4 dereferenceable(5) %206, ptr noundef nonnull align 4 dereferenceable(5) %13) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %14) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %13) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %12) #8
  br label %208

208:                                              ; preds = %192
  %209 = load i32, ptr %11, align 4, !tbaa !5
  %210 = add nsw i32 %209, 1
  store i32 %210, ptr %11, align 4, !tbaa !5
  br label %117, !llvm.loop !13

211:                                              ; preds = %120
  %212 = load i32, ptr %10, align 4, !tbaa !5
  %213 = sext i32 %212 to i64
  %214 = getelementptr inbounds [301 x %"class.std::vector"], ptr @e, i64 0, i64 %213
  %215 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE5beginEv(ptr noundef nonnull align 8 dereferenceable(24) %214) #8
  %216 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %15, i32 0, i32 0
  store ptr %215, ptr %216, align 8
  %217 = load i32, ptr %10, align 4, !tbaa !5
  %218 = sext i32 %217 to i64
  %219 = getelementptr inbounds [301 x %"class.std::vector"], ptr @e, i64 0, i64 %218
  %220 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE3endEv(ptr noundef nonnull align 8 dereferenceable(24) %219) #8
  %221 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %16, i32 0, i32 0
  store ptr %220, ptr %221, align 8
  %222 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %15, i32 0, i32 0
  %223 = load ptr, ptr %222, align 8
  %224 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %16, i32 0, i32 0
  %225 = load ptr, ptr %224, align 8
  call void @_ZSt4sortIN9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS3_SaIS3_EEEEEvT_S9_(ptr %223, ptr %225)
  %226 = load i32, ptr %10, align 4, !tbaa !5
  %227 = sext i32 %226 to i64
  %228 = getelementptr inbounds [301 x %"class.std::vector"], ptr @e, i64 0, i64 %227
  call void @llvm.lifetime.start.p0(i64 8, ptr %18) #8
  %229 = load i32, ptr %10, align 4, !tbaa !5
  %230 = sext i32 %229 to i64
  %231 = getelementptr inbounds [301 x %"class.std::vector"], ptr @e, i64 0, i64 %230
  %232 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE5beginEv(ptr noundef nonnull align 8 dereferenceable(24) %231) #8
  %233 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %19, i32 0, i32 0
  store ptr %232, ptr %233, align 8
  %234 = load i32, ptr %10, align 4, !tbaa !5
  %235 = sext i32 %234 to i64
  %236 = getelementptr inbounds [301 x %"class.std::vector"], ptr @e, i64 0, i64 %235
  %237 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE3endEv(ptr noundef nonnull align 8 dereferenceable(24) %236) #8
  %238 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %20, i32 0, i32 0
  store ptr %237, ptr %238, align 8
  %239 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %19, i32 0, i32 0
  %240 = load ptr, ptr %239, align 8
  %241 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %20, i32 0, i32 0
  %242 = load ptr, ptr %241, align 8
  %243 = call ptr @"_ZSt6uniqueIN9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS3_SaIS3_EEEEZ5solvevE3$_0ET_SA_SA_T0_"(ptr %240, ptr %242)
  %244 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %18, i32 0, i32 0
  store ptr %243, ptr %244, align 8
  call void @_ZN9__gnu_cxx17__normal_iteratorIPKSt4pairIicESt6vectorIS2_SaIS2_EEEC2IPS2_vEERKNS0_IT_S7_EE(ptr noundef nonnull align 8 dereferenceable(8) %17, ptr noundef nonnull align 8 dereferenceable(8) %18) #8
  call void @llvm.lifetime.start.p0(i64 8, ptr %23) #8
  %245 = load i32, ptr %10, align 4, !tbaa !5
  %246 = sext i32 %245 to i64
  %247 = getelementptr inbounds [301 x %"class.std::vector"], ptr @e, i64 0, i64 %246
  %248 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE3endEv(ptr noundef nonnull align 8 dereferenceable(24) %247) #8
  %249 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %23, i32 0, i32 0
  store ptr %248, ptr %249, align 8
  call void @_ZN9__gnu_cxx17__normal_iteratorIPKSt4pairIicESt6vectorIS2_SaIS2_EEEC2IPS2_vEERKNS0_IT_S7_EE(ptr noundef nonnull align 8 dereferenceable(8) %22, ptr noundef nonnull align 8 dereferenceable(8) %23) #8
  %250 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator.0", ptr %17, i32 0, i32 0
  %251 = load ptr, ptr %250, align 8
  %252 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator.0", ptr %22, i32 0, i32 0
  %253 = load ptr, ptr %252, align 8
  %254 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE5eraseEN9__gnu_cxx17__normal_iteratorIPKS1_S3_EES8_(ptr noundef nonnull align 8 dereferenceable(24) %228, ptr %251, ptr %253)
  %255 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %24, i32 0, i32 0
  store ptr %254, ptr %255, align 8
  call void @llvm.lifetime.end.p0(i64 8, ptr %23) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %18) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %10) #8
  br label %256

256:                                              ; preds = %211
  %257 = load i32, ptr %8, align 4, !tbaa !5
  %258 = add nsw i32 %257, 1
  store i32 %258, ptr %8, align 4, !tbaa !5
  br label %104, !llvm.loop !14

259:                                              ; preds = %108
  %260 = load i32, ptr @tot, align 4, !tbaa !5
  %261 = load i32, ptr %1, align 4, !tbaa !5
  %262 = shl i32 %260, %261
  %263 = sext i32 %262 to i64
  %264 = mul i64 %263, 4
  call void @llvm.memset.p0.i64(ptr align 16 @dis, i8 -1, i64 %264, i1 false)
  store i32 0, ptr @que, align 16, !tbaa !5
  store i32 0, ptr @dis, align 16, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %25) #8
  %265 = load i32, ptr %1, align 4, !tbaa !5
  %266 = shl i32 1, %265
  %267 = sub nsw i32 %266, 1
  store i32 %267, ptr %25, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %26) #8
  store i32 0, ptr %26, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %27) #8
  store i32 1, ptr %27, align 4, !tbaa !5
  br label %268

268:                                              ; preds = %388, %259
  %269 = load i32, ptr %26, align 4, !tbaa !5
  %270 = load i32, ptr %27, align 4, !tbaa !5
  %271 = icmp slt i32 %269, %270
  br i1 %271, label %273, label %272

272:                                              ; preds = %268
  store i32 14, ptr %4, align 4
  br label %391

273:                                              ; preds = %268
  call void @llvm.lifetime.start.p0(i64 4, ptr %28) #8
  %274 = load i32, ptr %26, align 4, !tbaa !5
  %275 = sext i32 %274 to i64
  %276 = getelementptr inbounds [10000001 x i32], ptr @que, i64 0, i64 %275
  %277 = load i32, ptr %276, align 4, !tbaa !5
  store i32 %277, ptr %28, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %29) #8
  %278 = load i32, ptr %28, align 4, !tbaa !5
  %279 = load i32, ptr %1, align 4, !tbaa !5
  %280 = ashr i32 %278, %279
  store i32 %280, ptr %29, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %30) #8
  %281 = load i32, ptr %28, align 4, !tbaa !5
  %282 = load i32, ptr %25, align 4, !tbaa !5
  %283 = and i32 %281, %282
  store i32 %283, ptr %30, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 8, ptr %31) #8
  %284 = load i32, ptr %29, align 4, !tbaa !5
  %285 = sext i32 %284 to i64
  %286 = getelementptr inbounds [301 x %"class.std::vector"], ptr @e, i64 0, i64 %285
  store ptr %286, ptr %31, align 8, !tbaa !15
  call void @llvm.lifetime.start.p0(i64 8, ptr %32) #8
  %287 = load ptr, ptr %31, align 8, !tbaa !15
  %288 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE5beginEv(ptr noundef nonnull align 8 dereferenceable(24) %287) #8
  %289 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %32, i32 0, i32 0
  store ptr %288, ptr %289, align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr %33) #8
  %290 = load ptr, ptr %31, align 8, !tbaa !15
  %291 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE3endEv(ptr noundef nonnull align 8 dereferenceable(24) %290) #8
  %292 = getelementptr inbounds %"class.__gnu_cxx::__normal_iterator", ptr %33, i32 0, i32 0
  store ptr %291, ptr %292, align 8
  br label %293

293:                                              ; preds = %380, %273
  %294 = call noundef zeroext i1 @_ZN9__gnu_cxxneIPSt4pairIicESt6vectorIS2_SaIS2_EEEEbRKNS_17__normal_iteratorIT_T0_EESC_(ptr noundef nonnull align 8 dereferenceable(8) %32, ptr noundef nonnull align 8 dereferenceable(8) %33) #8
  br i1 %294, label %296, label %295

295:                                              ; preds = %293
  store i32 17, ptr %4, align 4
  br label %382

296:                                              ; preds = %293
  call void @llvm.lifetime.start.p0(i64 8, ptr %34) #8
  %297 = call noundef nonnull align 4 dereferenceable(5) ptr @_ZNK9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS2_SaIS2_EEEdeEv(ptr noundef nonnull align 8 dereferenceable(8) %32) #8
  store ptr %297, ptr %34, align 8, !tbaa !15
  call void @llvm.lifetime.start.p0(i64 4, ptr %35) #8
  %298 = load ptr, ptr %34, align 8, !tbaa !15
  %299 = getelementptr inbounds %"struct.std::pair", ptr %298, i32 0, i32 0
  %300 = load i32, ptr %299, align 4, !tbaa !17
  store i32 %300, ptr %35, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %36) #8
  %301 = load i32, ptr %30, align 4, !tbaa !5
  %302 = load i32, ptr %35, align 4, !tbaa !5
  %303 = sext i32 %302 to i64
  %304 = getelementptr inbounds [301 x i32], ptr @msk, i64 0, i64 %303
  %305 = load i32, ptr %304, align 4, !tbaa !5
  %306 = or i32 %301, %305
  store i32 %306, ptr %36, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %37) #8
  %307 = load i32, ptr %35, align 4, !tbaa !5
  %308 = load i32, ptr %1, align 4, !tbaa !5
  %309 = shl i32 %307, %308
  %310 = load i32, ptr %36, align 4, !tbaa !5
  %311 = or i32 %309, %310
  store i32 %311, ptr %37, align 4, !tbaa !5
  %312 = load i32, ptr %36, align 4, !tbaa !5
  %313 = load i32, ptr %25, align 4, !tbaa !5
  %314 = icmp sgt i32 %312, %313
  br i1 %314, label %321, label %315

315:                                              ; preds = %296
  %316 = load i32, ptr %37, align 4, !tbaa !5
  %317 = sext i32 %316 to i64
  %318 = getelementptr inbounds [10000001 x i32], ptr @dis, i64 0, i64 %317
  %319 = load i32, ptr %318, align 4, !tbaa !5
  %320 = icmp ne i32 %319, -1
  br i1 %320, label %321, label %322

321:                                              ; preds = %315, %296
  store i32 18, ptr %4, align 4
  br label %374

322:                                              ; preds = %315
  %323 = load i32, ptr %28, align 4, !tbaa !5
  %324 = sext i32 %323 to i64
  %325 = getelementptr inbounds [10000001 x i32], ptr @dis, i64 0, i64 %324
  %326 = load i32, ptr %325, align 4, !tbaa !5
  %327 = add nsw i32 %326, 1
  %328 = load i32, ptr %37, align 4, !tbaa !5
  %329 = sext i32 %328 to i64
  %330 = getelementptr inbounds [10000001 x i32], ptr @dis, i64 0, i64 %329
  store i32 %327, ptr %330, align 4, !tbaa !5
  %331 = load i32, ptr %37, align 4, !tbaa !5
  %332 = load i32, ptr %27, align 4, !tbaa !5
  %333 = sext i32 %332 to i64
  %334 = getelementptr inbounds [10000001 x i32], ptr @que, i64 0, i64 %333
  store i32 %331, ptr %334, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 8, ptr %38) #8
  %335 = load ptr, ptr %34, align 8, !tbaa !15
  %336 = getelementptr inbounds %"struct.std::pair", ptr %335, i32 0, i32 1
  call void @_ZNSt4pairIicEC2IRiRcTnNSt9enable_ifIXaaclsr5_PCCPE22_MoveConstructiblePairIT_T0_EEclsr5_PCCPE30_ImplicitlyMoveConvertiblePairIS5_S6_EEEbE4typeELb1EEEOS5_OS6_(ptr noundef nonnull align 4 dereferenceable(5) %38, ptr noundef nonnull align 4 dereferenceable(4) %26, ptr noundef nonnull align 1 dereferenceable(1) %336)
  %337 = load i32, ptr %27, align 4, !tbaa !5
  %338 = sext i32 %337 to i64
  %339 = getelementptr inbounds [10000001 x %"struct.std::pair"], ptr @pre, i64 0, i64 %338
  %340 = call noundef nonnull align 4 dereferenceable(5) ptr @_ZNSt4pairIicEaSEOS0_(ptr noundef nonnull align 4 dereferenceable(5) %339, ptr noundef nonnull align 4 dereferenceable(5) %38) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %38) #8
  %341 = load i32, ptr %36, align 4, !tbaa !5
  %342 = load i32, ptr %25, align 4, !tbaa !5
  %343 = icmp eq i32 %341, %342
  br i1 %343, label %344, label %371

344:                                              ; preds = %322
  call void @llvm.lifetime.start.p0(i64 4, ptr %39) #8
  store i32 0, ptr %39, align 4, !tbaa !5
  br label %345

345:                                              ; preds = %348, %344
  %346 = load i32, ptr %27, align 4, !tbaa !5
  %347 = icmp sgt i32 %346, 0
  br i1 %347, label %348, label %363

348:                                              ; preds = %345
  %349 = load i32, ptr %27, align 4, !tbaa !5
  %350 = sext i32 %349 to i64
  %351 = getelementptr inbounds [10000001 x %"struct.std::pair"], ptr @pre, i64 0, i64 %350
  %352 = getelementptr inbounds %"struct.std::pair", ptr %351, i32 0, i32 1
  %353 = load i8, ptr %352, align 4, !tbaa !19
  %354 = load i32, ptr %39, align 4, !tbaa !5
  %355 = add nsw i32 %354, 1
  store i32 %355, ptr %39, align 4, !tbaa !5
  %356 = sext i32 %354 to i64
  %357 = getelementptr inbounds [4517 x i8], ptr @_ZZ5solvevE3out, i64 0, i64 %356
  store i8 %353, ptr %357, align 1, !tbaa !9
  %358 = load i32, ptr %27, align 4, !tbaa !5
  %359 = sext i32 %358 to i64
  %360 = getelementptr inbounds [10000001 x %"struct.std::pair"], ptr @pre, i64 0, i64 %359
  %361 = getelementptr inbounds %"struct.std::pair", ptr %360, i32 0, i32 0
  %362 = load i32, ptr %361, align 8, !tbaa !17
  store i32 %362, ptr %27, align 4, !tbaa !5
  br label %345, !llvm.loop !20

363:                                              ; preds = %345
  %364 = load i32, ptr %39, align 4, !tbaa !5
  %365 = sext i32 %364 to i64
  %366 = getelementptr inbounds i8, ptr @_ZZ5solvevE3out, i64 %365
  call void @_ZSt7reverseIPcEvT_S1_(ptr noundef @_ZZ5solvevE3out, ptr noundef %366)
  %367 = load i32, ptr %39, align 4, !tbaa !5
  %368 = sext i32 %367 to i64
  %369 = getelementptr inbounds [4517 x i8], ptr @_ZZ5solvevE3out, i64 0, i64 %368
  store i8 0, ptr %369, align 1, !tbaa !9
  %370 = call i32 @puts(ptr noundef @_ZZ5solvevE3out)
  store i32 1, ptr %4, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %39) #8
  br label %374

371:                                              ; preds = %322
  %372 = load i32, ptr %27, align 4, !tbaa !5
  %373 = add nsw i32 %372, 1
  store i32 %373, ptr %27, align 4, !tbaa !5
  store i32 0, ptr %4, align 4
  br label %374

374:                                              ; preds = %371, %363, %321
  call void @llvm.lifetime.end.p0(i64 4, ptr %37) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %36) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %35) #8
  %375 = load i32, ptr %4, align 4
  switch i32 %375, label %377 [
    i32 0, label %376
  ]

376:                                              ; preds = %374
  store i32 0, ptr %4, align 4
  br label %377

377:                                              ; preds = %376, %374
  call void @llvm.lifetime.end.p0(i64 8, ptr %34) #8
  %378 = load i32, ptr %4, align 4
  switch i32 %378, label %382 [
    i32 0, label %379
    i32 18, label %380
  ]

379:                                              ; preds = %377
  br label %380

380:                                              ; preds = %379, %377
  %381 = call noundef nonnull align 8 dereferenceable(8) ptr @_ZN9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS2_SaIS2_EEEppEv(ptr noundef nonnull align 8 dereferenceable(8) %32) #8
  br label %293

382:                                              ; preds = %377, %295
  call void @llvm.lifetime.end.p0(i64 8, ptr %33) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %32) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr %31) #8
  %383 = load i32, ptr %4, align 4
  switch i32 %383, label %385 [
    i32 17, label %384
  ]

384:                                              ; preds = %382
  store i32 0, ptr %4, align 4
  br label %385

385:                                              ; preds = %384, %382
  call void @llvm.lifetime.end.p0(i64 4, ptr %30) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %29) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %28) #8
  %386 = load i32, ptr %4, align 4
  switch i32 %386, label %391 [
    i32 0, label %387
  ]

387:                                              ; preds = %385
  br label %388

388:                                              ; preds = %387
  %389 = load i32, ptr %26, align 4, !tbaa !5
  %390 = add nsw i32 %389, 1
  store i32 %390, ptr %26, align 4, !tbaa !5
  br label %268, !llvm.loop !21

391:                                              ; preds = %385, %272
  call void @llvm.lifetime.end.p0(i64 4, ptr %27) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %26) #8
  %392 = load i32, ptr %4, align 4
  switch i32 %392, label %395 [
    i32 14, label %393
  ]

393:                                              ; preds = %391
  %394 = call i32 @puts(ptr noundef @.str.4)
  store i32 0, ptr %4, align 4
  br label %395

395:                                              ; preds = %393, %391
  call void @llvm.lifetime.end.p0(i64 4, ptr %25) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %2) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %1) #8
  %396 = load i32, ptr %4, align 4
  switch i32 %396, label %398 [
    i32 0, label %397
    i32 1, label %397
  ]

397:                                              ; preds = %395, %395
  ret void

398:                                              ; preds = %395
  unreachable
}

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

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

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local noundef i32 @_Z7newNodev() #3

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

; Function Attrs: nocallback nofree nounwind willreturn memory(argmem: readwrite)
declare void @llvm.memcpy.p0.p0.i64(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i64, i1 immarg) #4

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZNSt6vectorISt4pairIicESaIS1_EE6resizeEm(ptr noundef nonnull align 8 dereferenceable(24), i64 noundef) #0 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNSt4pairIicEC2IRiiTnNSt9enable_ifIXaaclsr5_PCCPE22_MoveConstructiblePairIT_T0_EEclsr5_PCCPE30_ImplicitlyMoveConvertiblePairIS4_S5_EEEbE4typeELb1EEEOS4_OS5_(ptr noundef nonnull align 4 dereferenceable(5), ptr noundef nonnull align 4 dereferenceable(4), ptr noundef nonnull align 4 dereferenceable(4)) unnamed_addr #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(5) ptr @_ZNSt6vectorISt4pairIicESaIS1_EEixEm(ptr noundef nonnull align 8 dereferenceable(24), i64 noundef) #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(5) ptr @_ZNSt4pairIicEaSEOS0_(ptr noundef nonnull align 4 dereferenceable(5), ptr noundef nonnull align 4 dereferenceable(5)) #5 align 2

; Function Attrs: inlinehint mustprogress uwtable
declare dso_local void @_ZSt4sortIN9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS3_SaIS3_EEEEEvT_S9_(ptr, ptr) #6

; Function Attrs: mustprogress nounwind uwtable
declare dso_local ptr @_ZNSt6vectorISt4pairIicESaIS1_EE5beginEv(ptr noundef nonnull align 8 dereferenceable(24)) #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local ptr @_ZNSt6vectorISt4pairIicESaIS1_EE3endEv(ptr noundef nonnull align 8 dereferenceable(24)) #5 align 2

; Function Attrs: mustprogress uwtable
declare dso_local ptr @_ZNSt6vectorISt4pairIicESaIS1_EE5eraseEN9__gnu_cxx17__normal_iteratorIPKS1_S3_EES8_(ptr noundef nonnull align 8 dereferenceable(24), ptr, ptr) #0 align 2

; Function Attrs: inlinehint mustprogress uwtable
declare hidden ptr @"_ZSt6uniqueIN9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS3_SaIS3_EEEEZ5solvevE3$_0ET_SA_SA_T0_"(ptr, ptr) #6

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZN9__gnu_cxx17__normal_iteratorIPKSt4pairIicESt6vectorIS2_SaIS2_EEEC2IPS2_vEERKNS0_IT_S7_EE(ptr noundef nonnull align 8 dereferenceable(8), ptr noundef nonnull align 8 dereferenceable(8)) unnamed_addr #5 align 2

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

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local noundef zeroext i1 @_ZN9__gnu_cxxneIPSt4pairIicESt6vectorIS2_SaIS2_EEEEbRKNS_17__normal_iteratorIT_T0_EESC_(ptr noundef nonnull align 8 dereferenceable(8), ptr noundef nonnull align 8 dereferenceable(8)) #3

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(5) ptr @_ZNK9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS2_SaIS2_EEEdeEv(ptr noundef nonnull align 8 dereferenceable(8)) #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNSt4pairIicEC2IRiRcTnNSt9enable_ifIXaaclsr5_PCCPE22_MoveConstructiblePairIT_T0_EEclsr5_PCCPE30_ImplicitlyMoveConvertiblePairIS5_S6_EEEbE4typeELb1EEEOS5_OS6_(ptr noundef nonnull align 4 dereferenceable(5), ptr noundef nonnull align 4 dereferenceable(4), ptr noundef nonnull align 1 dereferenceable(1)) unnamed_addr #5 align 2

; Function Attrs: inlinehint mustprogress uwtable
declare dso_local void @_ZSt7reverseIPcEvT_S1_(ptr noundef, ptr noundef) #6

declare i32 @puts(ptr noundef) #2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 8 dereferenceable(8) ptr @_ZN9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS2_SaIS2_EEEppEv(ptr noundef nonnull align 8 dereferenceable(8)) #5 align 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 = { nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
attributes #2 = { "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 = { inlinehint mustprogress nounwind 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 #4 = { nocallback nofree nounwind willreturn memory(argmem: readwrite) }
attributes #5 = { mustprogress nounwind 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 = { 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 #7 = { nocallback nofree nounwind willreturn memory(argmem: write) }
attributes #8 = { 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 = !{!7, !7, i64 0}
!10 = distinct !{!10, !11}
!11 = !{!"llvm.loop.mustprogress"}
!12 = distinct !{!12, !11}
!13 = distinct !{!13, !11}
!14 = distinct !{!14, !11}
!15 = !{!16, !16, i64 0}
!16 = !{!"any pointer", !7, i64 0}
!17 = !{!18, !6, i64 0}
!18 = !{!"_ZTSSt4pairIicE", !6, i64 0, !7, i64 4}
!19 = !{!18, !7, i64 4}
!20 = distinct !{!20, !11}
!21 = distinct !{!21, !11}


; 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"

%"class.std::vector" = type { %"struct.std::_Vector_base" }
%"struct.std::_Vector_base" = type { %"struct.std::_Vector_base<std::pair<int, char>, std::allocator<std::pair<int, char>>>::_Vector_impl" }
%"struct.std::_Vector_base<std::pair<int, char>, std::allocator<std::pair<int, char>>>::_Vector_impl" = type { %"struct.std::_Vector_base<std::pair<int, char>, std::allocator<std::pair<int, char>>>::_Vector_impl_data" }
%"struct.std::_Vector_base<std::pair<int, char>, std::allocator<std::pair<int, char>>>::_Vector_impl_data" = type { ptr, ptr, ptr }
%"struct.std::pair" = type <{ i32, i8, [3 x i8] }>
%"class.__gnu_cxx::__normal_iterator.0" = type { ptr }
%"class.__gnu_cxx::__normal_iterator" = type { ptr }

@tot = external dso_local local_unnamed_addr global i32, align 4
@msk = external dso_local local_unnamed_addr global [301 x i32], align 16
@sub = external dso_local local_unnamed_addr global [301 x [11 x i32]], align 16
@f = external dso_local local_unnamed_addr global [301 x i32], align 16
@nxt = external dso_local global [301 x [11 x i32]], align 16
@e = external dso_local global [301 x %"class.std::vector"], align 16
@que = external dso_local local_unnamed_addr global [10000001 x i32], align 16
@dis = external dso_local local_unnamed_addr global [10000001 x i32], align 16
@pre = external dso_local global [10000001 x %"struct.std::pair"], align 16
@_ZZ5solvevE3buf = external hidden global [301 x i8], align 16
@.str = external hidden unnamed_addr constant [5 x i8], align 1
@.str.3 = external hidden unnamed_addr constant [3 x i8], align 1
@_ZZ5solvevE3out = external hidden global [4517 x i8], align 16
@.str.4 = external hidden unnamed_addr constant [2 x i8], align 1

; Function Attrs: mustprogress uwtable
define dso_local void @_Z5solvev() local_unnamed_addr #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  %3 = alloca %"struct.std::pair", align 4
  %4 = alloca i32, align 4
  %5 = alloca %"class.__gnu_cxx::__normal_iterator.0", align 8
  %6 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %7 = alloca %"class.__gnu_cxx::__normal_iterator.0", align 8
  %8 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %9 = alloca i32, align 4
  %10 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %11 = alloca %"class.__gnu_cxx::__normal_iterator", align 8
  %12 = alloca %"struct.std::pair", align 4
  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %1) #8
  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %2) #8
  %13 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef nonnull @.str, ptr noundef nonnull %1, ptr noundef nonnull %2)
  store i32 0, ptr @tot, align 4, !tbaa !5
  %14 = call noundef i32 @_Z7newNodev()
  %15 = load i32, ptr %1, align 4, !tbaa !5
  %16 = load i32, ptr %2, align 4, !tbaa !5
  %17 = add nsw i32 %16, %15
  %18 = icmp sgt i32 %17, 0
  br i1 %18, label %.lr.ph126, label %._crit_edge127

._crit_edge127:                                   ; preds = %._crit_edge, %0
  store i32 0, ptr @que, align 16, !tbaa !5
  store i32 0, ptr @f, align 16, !tbaa !5
  call void @llvm.memcpy.p0.p0.i64(ptr noundef nonnull align 16 dereferenceable(40) @nxt, ptr noundef nonnull align 16 dereferenceable(40) @sub, i64 40, i1 false)
  br label %50

.lr.ph126:                                        ; preds = %0, %._crit_edge
  %.091124 = phi i32 [ %26, %._crit_edge ], [ 0, %0 ]
  %19 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef nonnull @.str.3, ptr noundef nonnull @_ZZ5solvevE3buf)
  %20 = load i8, ptr @_ZZ5solvevE3buf, align 16, !tbaa !9
  %.not112121 = icmp eq i8 %20, 0
  br i1 %.not112121, label %._crit_edge, label %.lr.ph

._crit_edge:                                      ; preds = %39, %.lr.ph126
  %.093.lcssa = phi i32 [ 0, %.lr.ph126 ], [ %40, %39 ]
  %21 = shl nuw i32 1, %.091124
  %22 = sext i32 %.093.lcssa to i64
  %23 = getelementptr inbounds [301 x i32], ptr @msk, i64 0, i64 %22
  %24 = load i32, ptr %23, align 4, !tbaa !5
  %25 = or i32 %24, %21
  store i32 %25, ptr %23, align 4, !tbaa !5
  %26 = add nuw nsw i32 %.091124, 1
  %27 = load i32, ptr %1, align 4, !tbaa !5
  %28 = load i32, ptr %2, align 4, !tbaa !5
  %29 = add nsw i32 %28, %27
  %30 = icmp slt i32 %26, %29
  br i1 %30, label %.lr.ph126, label %._crit_edge127, !llvm.loop !10

.lr.ph:                                           ; preds = %.lr.ph126, %39
  %indvars.iv = phi i64 [ %indvars.iv.next, %39 ], [ 0, %.lr.ph126 ]
  %31 = phi i8 [ %42, %39 ], [ %20, %.lr.ph126 ]
  %.093123 = phi i32 [ %40, %39 ], [ 0, %.lr.ph126 ]
  %32 = sext i8 %31 to i64
  %33 = add nsw i64 %32, -97
  %34 = sext i32 %.093123 to i64
  %35 = getelementptr inbounds [301 x [11 x i32]], ptr @sub, i64 0, i64 %34, i64 %33
  %36 = load i32, ptr %35, align 4, !tbaa !5
  %.not113 = icmp eq i32 %36, 0
  br i1 %.not113, label %37, label %39

37:                                               ; preds = %.lr.ph
  %38 = call noundef i32 @_Z7newNodev()
  store i32 %38, ptr %35, align 4, !tbaa !5
  br label %39

39:                                               ; preds = %37, %.lr.ph
  %40 = phi i32 [ %38, %37 ], [ %36, %.lr.ph ]
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %41 = getelementptr inbounds [301 x i8], ptr @_ZZ5solvevE3buf, i64 0, i64 %indvars.iv.next
  %42 = load i8, ptr %41, align 1, !tbaa !9
  %.not112 = icmp eq i8 %42, 0
  br i1 %.not112, label %._crit_edge, label %.lr.ph, !llvm.loop !12

43:                                               ; preds = %.split131.us
  %44 = load i32, ptr @tot, align 4, !tbaa !5
  %45 = load i32, ptr %1, align 4, !tbaa !5
  %46 = shl i32 %44, %45
  %47 = sext i32 %46 to i64
  %48 = shl nsw i64 %47, 2
  call void @llvm.memset.p0.i64(ptr nonnull align 16 @dis, i8 -1, i64 %48, i1 false)
  store i32 0, ptr @que, align 16, !tbaa !5
  store i32 0, ptr @dis, align 16, !tbaa !5
  %notmask = shl nsw i32 -1, %45
  %49 = xor i32 %notmask, -1
  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %9) #8
  store i32 0, ptr %9, align 4, !tbaa !5
  br label %114

50:                                               ; preds = %._crit_edge127, %.split131.us
  %indvars.iv156 = phi i64 [ 0, %._crit_edge127 ], [ %indvars.iv.next157, %.split131.us ]
  %.096132 = phi i32 [ 1, %._crit_edge127 ], [ %.us-phi, %.split131.us ]
  %51 = getelementptr inbounds [10000001 x i32], ptr @que, i64 0, i64 %indvars.iv156
  %52 = load i32, ptr %51, align 4, !tbaa !5
  %.fr = freeze i32 %52
  %53 = sext i32 %.fr to i64
  %54 = getelementptr inbounds [301 x %"class.std::vector"], ptr @e, i64 0, i64 %53
  call void @_ZNSt6vectorISt4pairIicESaIS1_EE6resizeEm(ptr noundef nonnull align 8 dereferenceable(24) %54, i64 noundef 10)
  %.not111 = icmp eq i32 %.fr, 0
  %55 = getelementptr inbounds [301 x i32], ptr @f, i64 0, i64 %53
  br i1 %.not111, label %.split.us, label %.split

.split.us:                                        ; preds = %50, %73
  %indvars.iv152 = phi i64 [ %indvars.iv.next153, %73 ], [ 0, %50 ]
  %.197129.us = phi i32 [ %.298.us, %73 ], [ %.096132, %50 ]
  %56 = getelementptr inbounds [301 x [11 x i32]], ptr @sub, i64 0, i64 %53, i64 %indvars.iv152
  %57 = load i32, ptr %56, align 4, !tbaa !5
  %.not110.us = icmp eq i32 %57, 0
  br i1 %.not110.us, label %68, label %58

58:                                               ; preds = %.split.us
  %59 = sext i32 %57 to i64
  %60 = getelementptr inbounds [301 x i32], ptr @f, i64 0, i64 %59
  store i32 0, ptr %60, align 4, !tbaa !5
  %61 = load i32, ptr @msk, align 16, !tbaa !5
  %62 = getelementptr inbounds [301 x i32], ptr @msk, i64 0, i64 %59
  %63 = load i32, ptr %62, align 4, !tbaa !5
  %64 = or i32 %63, %61
  store i32 %64, ptr %62, align 4, !tbaa !5
  %65 = add nsw i32 %.197129.us, 1
  %66 = sext i32 %.197129.us to i64
  %67 = getelementptr inbounds [10000001 x i32], ptr @que, i64 0, i64 %66
  store i32 %57, ptr %67, align 4, !tbaa !5
  br label %73

68:                                               ; preds = %.split.us
  %69 = load i32, ptr %55, align 4, !tbaa !5
  %70 = sext i32 %69 to i64
  %71 = getelementptr inbounds [301 x [11 x i32]], ptr @nxt, i64 0, i64 %70, i64 %indvars.iv152
  %72 = load i32, ptr %71, align 4, !tbaa !5
  br label %73

73:                                               ; preds = %68, %58
  %.sink = phi i32 [ %72, %68 ], [ %57, %58 ]
  %.298.us = phi i32 [ %.197129.us, %68 ], [ %65, %58 ]
  %74 = getelementptr inbounds [301 x [11 x i32]], ptr @nxt, i64 0, i64 %53, i64 %indvars.iv152
  store i32 %.sink, ptr %74, align 4
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %3) #8
  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %4) #8
  %75 = trunc i64 %indvars.iv152 to i32
  %76 = add i32 %75, 97
  store i32 %76, ptr %4, align 4, !tbaa !5
  call void @_ZNSt4pairIicEC2IRiiTnNSt9enable_ifIXaaclsr5_PCCPE22_MoveConstructiblePairIT_T0_EEclsr5_PCCPE30_ImplicitlyMoveConvertiblePairIS4_S5_EEEbE4typeELb1EEEOS4_OS5_(ptr noundef nonnull align 4 dereferenceable(5) %3, ptr noundef nonnull align 4 dereferenceable(4) %74, ptr noundef nonnull align 4 dereferenceable(4) %4)
  %77 = call noundef nonnull align 4 dereferenceable(5) ptr @_ZNSt6vectorISt4pairIicESaIS1_EEixEm(ptr noundef nonnull align 8 dereferenceable(24) %54, i64 noundef %indvars.iv152) #8
  %78 = call noundef nonnull align 4 dereferenceable(5) ptr @_ZNSt4pairIicEaSEOS0_(ptr noundef nonnull align 4 dereferenceable(5) %77, ptr noundef nonnull align 4 dereferenceable(5) %3) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %4) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %3) #8
  %indvars.iv.next153 = add nuw nsw i64 %indvars.iv152, 1
  %exitcond155.not = icmp eq i64 %indvars.iv.next153, 10
  br i1 %exitcond155.not, label %.split131.us, label %.split.us, !llvm.loop !13

.split131.us:                                     ; preds = %108, %73
  %.us-phi = phi i32 [ %.298.us, %73 ], [ %.298, %108 ]
  %79 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE5beginEv(ptr noundef nonnull align 8 dereferenceable(24) %54) #8
  %80 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE3endEv(ptr noundef nonnull align 8 dereferenceable(24) %54) #8
  call void @_ZSt4sortIN9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS3_SaIS3_EEEEEvT_S9_(ptr %79, ptr %80)
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %6) #8
  %81 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE5beginEv(ptr noundef nonnull align 8 dereferenceable(24) %54) #8
  %82 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE3endEv(ptr noundef nonnull align 8 dereferenceable(24) %54) #8
  %83 = call ptr @"_ZSt6uniqueIN9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS3_SaIS3_EEEEZ5solvevE3$_0ET_SA_SA_T0_"(ptr %81, ptr %82)
  store ptr %83, ptr %6, align 8
  call void @_ZN9__gnu_cxx17__normal_iteratorIPKSt4pairIicESt6vectorIS2_SaIS2_EEEC2IPS2_vEERKNS0_IT_S7_EE(ptr noundef nonnull align 8 dereferenceable(8) %5, ptr noundef nonnull align 8 dereferenceable(8) %6) #8
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %8) #8
  %84 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE3endEv(ptr noundef nonnull align 8 dereferenceable(24) %54) #8
  store ptr %84, ptr %8, align 8
  call void @_ZN9__gnu_cxx17__normal_iteratorIPKSt4pairIicESt6vectorIS2_SaIS2_EEEC2IPS2_vEERKNS0_IT_S7_EE(ptr noundef nonnull align 8 dereferenceable(8) %7, ptr noundef nonnull align 8 dereferenceable(8) %8) #8
  %85 = load ptr, ptr %5, align 8
  %86 = load ptr, ptr %7, align 8
  %87 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE5eraseEN9__gnu_cxx17__normal_iteratorIPKS1_S3_EES8_(ptr noundef nonnull align 8 dereferenceable(24) %54, ptr %85, ptr %86)
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %8) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %6) #8
  %indvars.iv.next157 = add nuw nsw i64 %indvars.iv156, 1
  %88 = sext i32 %.us-phi to i64
  %89 = icmp slt i64 %indvars.iv.next157, %88
  br i1 %89, label %50, label %43, !llvm.loop !14

.split:                                           ; preds = %50, %108
  %indvars.iv149 = phi i64 [ %indvars.iv.next150, %108 ], [ 0, %50 ]
  %.197129 = phi i32 [ %.298, %108 ], [ %.096132, %50 ]
  %90 = getelementptr inbounds [301 x [11 x i32]], ptr @sub, i64 0, i64 %53, i64 %indvars.iv149
  %91 = load i32, ptr %90, align 4, !tbaa !5
  %.not110 = icmp eq i32 %91, 0
  %92 = load i32, ptr %55, align 4, !tbaa !5
  %93 = sext i32 %92 to i64
  %94 = getelementptr inbounds [301 x [11 x i32]], ptr @nxt, i64 0, i64 %93, i64 %indvars.iv149
  %95 = load i32, ptr %94, align 4, !tbaa !5
  br i1 %.not110, label %108, label %96

96:                                               ; preds = %.split
  %97 = sext i32 %91 to i64
  %98 = getelementptr inbounds [301 x i32], ptr @f, i64 0, i64 %97
  store i32 %95, ptr %98, align 4, !tbaa !5
  %99 = sext i32 %95 to i64
  %100 = getelementptr inbounds [301 x i32], ptr @msk, i64 0, i64 %99
  %101 = load i32, ptr %100, align 4, !tbaa !5
  %102 = getelementptr inbounds [301 x i32], ptr @msk, i64 0, i64 %97
  %103 = load i32, ptr %102, align 4, !tbaa !5
  %104 = or i32 %103, %101
  store i32 %104, ptr %102, align 4, !tbaa !5
  %105 = add nsw i32 %.197129, 1
  %106 = sext i32 %.197129 to i64
  %107 = getelementptr inbounds [10000001 x i32], ptr @que, i64 0, i64 %106
  store i32 %91, ptr %107, align 4, !tbaa !5
  br label %108

108:                                              ; preds = %.split, %96
  %.sink162 = phi i32 [ %91, %96 ], [ %95, %.split ]
  %.298 = phi i32 [ %105, %96 ], [ %.197129, %.split ]
  %109 = getelementptr inbounds [301 x [11 x i32]], ptr @nxt, i64 0, i64 %53, i64 %indvars.iv149
  store i32 %.sink162, ptr %109, align 4
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %3) #8
  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %4) #8
  %110 = trunc i64 %indvars.iv149 to i32
  %111 = add i32 %110, 97
  store i32 %111, ptr %4, align 4, !tbaa !5
  call void @_ZNSt4pairIicEC2IRiiTnNSt9enable_ifIXaaclsr5_PCCPE22_MoveConstructiblePairIT_T0_EEclsr5_PCCPE30_ImplicitlyMoveConvertiblePairIS4_S5_EEEbE4typeELb1EEEOS4_OS5_(ptr noundef nonnull align 4 dereferenceable(5) %3, ptr noundef nonnull align 4 dereferenceable(4) %109, ptr noundef nonnull align 4 dereferenceable(4) %4)
  %112 = call noundef nonnull align 4 dereferenceable(5) ptr @_ZNSt6vectorISt4pairIicESaIS1_EEixEm(ptr noundef nonnull align 8 dereferenceable(24) %54, i64 noundef %indvars.iv149) #8
  %113 = call noundef nonnull align 4 dereferenceable(5) ptr @_ZNSt4pairIicEaSEOS0_(ptr noundef nonnull align 4 dereferenceable(5) %112, ptr noundef nonnull align 4 dereferenceable(5) %3) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %4) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %3) #8
  %indvars.iv.next150 = add nuw nsw i64 %indvars.iv149, 1
  %exitcond.not = icmp eq i64 %indvars.iv.next150, 10
  br i1 %exitcond.not, label %.split131.us, label %.split, !llvm.loop !13

114:                                              ; preds = %43, %._crit_edge137
  %.0100140 = phi i32 [ 1, %43 ], [ %.1101.lcssa, %._crit_edge137 ]
  %storemerge139 = phi i32 [ 0, %43 ], [ %166, %._crit_edge137 ]
  %115 = sext i32 %storemerge139 to i64
  %116 = getelementptr inbounds [10000001 x i32], ptr @que, i64 0, i64 %115
  %117 = load i32, ptr %116, align 4, !tbaa !5
  %118 = load i32, ptr %1, align 4, !tbaa !5
  %119 = ashr i32 %117, %118
  %120 = and i32 %117, %49
  %121 = sext i32 %119 to i64
  %122 = getelementptr inbounds [301 x %"class.std::vector"], ptr @e, i64 0, i64 %121
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %10) #8
  %123 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE5beginEv(ptr noundef nonnull align 8 dereferenceable(24) %122) #8
  store ptr %123, ptr %10, align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %11) #8
  %124 = call ptr @_ZNSt6vectorISt4pairIicESaIS1_EE3endEv(ptr noundef nonnull align 8 dereferenceable(24) %122) #8
  store ptr %124, ptr %11, align 8
  %125 = call noundef zeroext i1 @_ZN9__gnu_cxxneIPSt4pairIicESt6vectorIS2_SaIS2_EEEEbRKNS_17__normal_iteratorIT_T0_EESC_(ptr noundef nonnull align 8 dereferenceable(8) %10, ptr noundef nonnull align 8 dereferenceable(8) %11) #8
  br i1 %125, label %.lr.ph136, label %._crit_edge137

.lr.ph136:                                        ; preds = %114
  %126 = sext i32 %117 to i64
  %127 = getelementptr inbounds [10000001 x i32], ptr @dis, i64 0, i64 %126
  br label %128

128:                                              ; preds = %.lr.ph136, %162
  %.1101134 = phi i32 [ %.0100140, %.lr.ph136 ], [ %.3.ph, %162 ]
  %129 = call noundef nonnull align 4 dereferenceable(5) ptr @_ZNK9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS2_SaIS2_EEEdeEv(ptr noundef nonnull align 8 dereferenceable(8) %10) #8
  %130 = load i32, ptr %129, align 4, !tbaa !15
  %131 = sext i32 %130 to i64
  %132 = getelementptr inbounds [301 x i32], ptr @msk, i64 0, i64 %131
  %133 = load i32, ptr %132, align 4, !tbaa !5
  %134 = or i32 %133, %120
  %135 = load i32, ptr %1, align 4, !tbaa !5
  %136 = shl i32 %130, %135
  %137 = or i32 %136, %134
  %138 = icmp sgt i32 %134, %49
  br i1 %138, label %162, label %139

139:                                              ; preds = %128
  %140 = sext i32 %137 to i64
  %141 = getelementptr inbounds [10000001 x i32], ptr @dis, i64 0, i64 %140
  %142 = load i32, ptr %141, align 4, !tbaa !5
  %.not = icmp eq i32 %142, -1
  br i1 %.not, label %143, label %162

143:                                              ; preds = %139
  %144 = load i32, ptr %127, align 4, !tbaa !5
  %145 = add nsw i32 %144, 1
  store i32 %145, ptr %141, align 4, !tbaa !5
  %146 = sext i32 %.1101134 to i64
  %147 = getelementptr inbounds [10000001 x i32], ptr @que, i64 0, i64 %146
  store i32 %137, ptr %147, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %12) #8
  %148 = getelementptr inbounds i8, ptr %129, i64 4
  call void @_ZNSt4pairIicEC2IRiRcTnNSt9enable_ifIXaaclsr5_PCCPE22_MoveConstructiblePairIT_T0_EEclsr5_PCCPE30_ImplicitlyMoveConvertiblePairIS5_S6_EEEbE4typeELb1EEEOS5_OS6_(ptr noundef nonnull align 4 dereferenceable(5) %12, ptr noundef nonnull align 4 dereferenceable(4) %9, ptr noundef nonnull align 1 dereferenceable(1) %148)
  %149 = getelementptr inbounds [10000001 x %"struct.std::pair"], ptr @pre, i64 0, i64 %146
  %150 = call noundef nonnull align 4 dereferenceable(5) ptr @_ZNSt4pairIicEaSEOS0_(ptr noundef nonnull align 4 dereferenceable(5) %149, ptr noundef nonnull align 4 dereferenceable(5) %12) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %12) #8
  %151 = icmp eq i32 %134, %49
  br i1 %151, label %.preheader, label %160

.preheader:                                       ; preds = %143
  %152 = icmp sgt i32 %.1101134, 0
  br i1 %152, label %.lr.ph143, label %._crit_edge144

.lr.ph143:                                        ; preds = %.preheader, %.lr.ph143
  %indvars.iv159 = phi i64 [ %indvars.iv.next160, %.lr.ph143 ], [ 0, %.preheader ]
  %.2102141 = phi i32 [ %158, %.lr.ph143 ], [ %.1101134, %.preheader ]
  %153 = zext nneg i32 %.2102141 to i64
  %154 = getelementptr inbounds [10000001 x %"struct.std::pair"], ptr @pre, i64 0, i64 %153
  %155 = getelementptr inbounds i8, ptr %154, i64 4
  %156 = load i8, ptr %155, align 4, !tbaa !17
  %indvars.iv.next160 = add nuw nsw i64 %indvars.iv159, 1
  %157 = getelementptr inbounds [4517 x i8], ptr @_ZZ5solvevE3out, i64 0, i64 %indvars.iv159
  store i8 %156, ptr %157, align 1, !tbaa !9
  %158 = load i32, ptr %154, align 8, !tbaa !15
  %159 = icmp sgt i32 %158, 0
  br i1 %159, label %.lr.ph143, label %._crit_edge144.loopexit, !llvm.loop !18

160:                                              ; preds = %143
  %161 = add nsw i32 %.1101134, 1
  br label %162

162:                                              ; preds = %160, %139, %128
  %.3.ph = phi i32 [ %.1101134, %128 ], [ %.1101134, %139 ], [ %161, %160 ]
  %163 = call noundef nonnull align 8 dereferenceable(8) ptr @_ZN9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS2_SaIS2_EEEppEv(ptr noundef nonnull align 8 dereferenceable(8) %10) #8
  %164 = call noundef zeroext i1 @_ZN9__gnu_cxxneIPSt4pairIicESt6vectorIS2_SaIS2_EEEEbRKNS_17__normal_iteratorIT_T0_EESC_(ptr noundef nonnull align 8 dereferenceable(8) %10, ptr noundef nonnull align 8 dereferenceable(8) %11) #8
  br i1 %164, label %128, label %._crit_edge137

._crit_edge137:                                   ; preds = %162, %114
  %.1101.lcssa = phi i32 [ %.0100140, %114 ], [ %.3.ph, %162 ]
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %11) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %10) #8
  %165 = load i32, ptr %9, align 4, !tbaa !5
  %166 = add nsw i32 %165, 1
  store i32 %166, ptr %9, align 4, !tbaa !5
  %.not108 = icmp slt i32 %166, %.1101.lcssa
  br i1 %.not108, label %114, label %170, !llvm.loop !19

._crit_edge144.loopexit:                          ; preds = %.lr.ph143
  %167 = and i64 %indvars.iv.next160, 4294967295
  br label %._crit_edge144

._crit_edge144:                                   ; preds = %._crit_edge144.loopexit, %.preheader
  %.0.lcssa = phi i64 [ 0, %.preheader ], [ %167, %._crit_edge144.loopexit ]
  %168 = getelementptr inbounds i8, ptr @_ZZ5solvevE3out, i64 %.0.lcssa
  call void @_ZSt7reverseIPcEvT_S1_(ptr noundef nonnull @_ZZ5solvevE3out, ptr noundef nonnull %168)
  store i8 0, ptr %168, align 1, !tbaa !9
  %169 = call i32 @puts(ptr noundef nonnull dereferenceable(1) @_ZZ5solvevE3out)
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %11) #8
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %10) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %9) #8
  br label %172

170:                                              ; preds = %._crit_edge137
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %9) #8
  %171 = call i32 @puts(ptr noundef nonnull dereferenceable(1) @.str.4)
  br label %172

172:                                              ; preds = %._crit_edge144, %170
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %2) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %1) #8
  ret void
}

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

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

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local noundef i32 @_Z7newNodev() local_unnamed_addr #3

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

; Function Attrs: mustprogress nocallback nofree nounwind willreturn memory(argmem: readwrite)
declare void @llvm.memcpy.p0.p0.i64(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i64, i1 immarg) #4

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZNSt6vectorISt4pairIicESaIS1_EE6resizeEm(ptr noundef nonnull align 8 dereferenceable(24), i64 noundef) local_unnamed_addr #0 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNSt4pairIicEC2IRiiTnNSt9enable_ifIXaaclsr5_PCCPE22_MoveConstructiblePairIT_T0_EEclsr5_PCCPE30_ImplicitlyMoveConvertiblePairIS4_S5_EEEbE4typeELb1EEEOS4_OS5_(ptr noundef nonnull align 4 dereferenceable(5), ptr noundef nonnull align 4 dereferenceable(4), ptr noundef nonnull align 4 dereferenceable(4)) unnamed_addr #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(5) ptr @_ZNSt6vectorISt4pairIicESaIS1_EEixEm(ptr noundef nonnull align 8 dereferenceable(24), i64 noundef) local_unnamed_addr #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(5) ptr @_ZNSt4pairIicEaSEOS0_(ptr noundef nonnull align 4 dereferenceable(5), ptr noundef nonnull align 4 dereferenceable(5)) local_unnamed_addr #5 align 2

; Function Attrs: inlinehint mustprogress uwtable
declare dso_local void @_ZSt4sortIN9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS3_SaIS3_EEEEEvT_S9_(ptr, ptr) local_unnamed_addr #6

; Function Attrs: mustprogress nounwind uwtable
declare dso_local ptr @_ZNSt6vectorISt4pairIicESaIS1_EE5beginEv(ptr noundef nonnull align 8 dereferenceable(24)) local_unnamed_addr #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local ptr @_ZNSt6vectorISt4pairIicESaIS1_EE3endEv(ptr noundef nonnull align 8 dereferenceable(24)) local_unnamed_addr #5 align 2

; Function Attrs: mustprogress uwtable
declare dso_local ptr @_ZNSt6vectorISt4pairIicESaIS1_EE5eraseEN9__gnu_cxx17__normal_iteratorIPKS1_S3_EES8_(ptr noundef nonnull align 8 dereferenceable(24), ptr, ptr) local_unnamed_addr #0 align 2

; Function Attrs: inlinehint mustprogress uwtable
declare hidden ptr @"_ZSt6uniqueIN9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS3_SaIS3_EEEEZ5solvevE3$_0ET_SA_SA_T0_"(ptr, ptr) local_unnamed_addr #6

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZN9__gnu_cxx17__normal_iteratorIPKSt4pairIicESt6vectorIS2_SaIS2_EEEC2IPS2_vEERKNS0_IT_S7_EE(ptr noundef nonnull align 8 dereferenceable(8), ptr noundef nonnull align 8 dereferenceable(8)) unnamed_addr #5 align 2

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

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local noundef zeroext i1 @_ZN9__gnu_cxxneIPSt4pairIicESt6vectorIS2_SaIS2_EEEEbRKNS_17__normal_iteratorIT_T0_EESC_(ptr noundef nonnull align 8 dereferenceable(8), ptr noundef nonnull align 8 dereferenceable(8)) local_unnamed_addr #3

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(5) ptr @_ZNK9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS2_SaIS2_EEEdeEv(ptr noundef nonnull align 8 dereferenceable(8)) local_unnamed_addr #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZNSt4pairIicEC2IRiRcTnNSt9enable_ifIXaaclsr5_PCCPE22_MoveConstructiblePairIT_T0_EEclsr5_PCCPE30_ImplicitlyMoveConvertiblePairIS5_S6_EEEbE4typeELb1EEEOS5_OS6_(ptr noundef nonnull align 4 dereferenceable(5), ptr noundef nonnull align 4 dereferenceable(4), ptr noundef nonnull align 1 dereferenceable(1)) unnamed_addr #5 align 2

; Function Attrs: inlinehint mustprogress uwtable
declare dso_local void @_ZSt7reverseIPcEvT_S1_(ptr noundef, ptr noundef) local_unnamed_addr #6

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

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef nonnull align 8 dereferenceable(8) ptr @_ZN9__gnu_cxx17__normal_iteratorIPSt4pairIicESt6vectorIS2_SaIS2_EEEppEv(ptr noundef nonnull align 8 dereferenceable(8)) local_unnamed_addr #5 align 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 nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
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 = { inlinehint mustprogress nounwind 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 #4 = { mustprogress nocallback nofree nounwind willreturn memory(argmem: readwrite) }
attributes #5 = { mustprogress nounwind 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 = { 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 #7 = { mustprogress nocallback nofree nounwind willreturn memory(argmem: write) }
attributes #8 = { 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 = !{!7, !7, i64 0}
!10 = distinct !{!10, !11}
!11 = !{!"llvm.loop.mustprogress"}
!12 = distinct !{!12, !11}
!13 = distinct !{!13, !11}
!14 = distinct !{!14, !11}
!15 = !{!16, !6, i64 0}
!16 = !{!"_ZTSSt4pairIicE", !6, i64 0, !7, i64 4}
!17 = !{!16, !7, i64 4}
!18 = distinct !{!18, !11}
!19 = distinct !{!19, !11}


; Effective O3 passes: CorrelatedValuePropagationPass,EarlyCSEPass,GVNPass,GlobalOptPass,IPSCCPPass,IndVarSimplifyPass,InferAlignmentPass,InferFunctionAttrsPass,InstCombinePass,InstSimplifyPass,JumpThreadingPass,LCSSAPass,LICMPass,LoopInstSimplifyPass,LoopRotatePass,LoopSimplifyCFGPass,LoopSimplifyPass,LoopUnrollPass,MergedLoadStoreMotionPass,ReassociatePass,SROAPass,SimplifyCFGPass